﻿// Hashtable.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <stdio.h>
#include "head.h"
#include "MinStack.h"
#include "MyQueue.h"
#include "isPalindrome.h"
#include "sort.h"
#include <list>
#include <map>
#include <forward_list>
#include <unordered_map>
#include <unordered_set>
#include <numeric>
#include <algorithm>
#include <functional>
#include "mytemplate.h"
#include "leetcode.h"
#include "struct.h"
#include "tree.h"
#include "tt.h"
#include "MyMaxQueue.h"
#include "Codec.h"

//#include <stl_construct.h>

using namespace std;

/*
int ret(int in) { return in * in; }

template<class T>
struct Display {
    void operator()(const T& x) const 
    {
        cout << x << " ";
    }
};

template<class T>
struct display {
    void operator()(const T& x) const
    {
        cout << x << " ";
    }
};

//仿函数，带参数
struct even {
    bool operator()(int x) const
    {
        return x % 2 ? false : true;
    }
};

//仿函数，无参数
class even_by_two
{
public:
    int operator()()
    {
        return _x += 2;
    }
private:
    static int _x;
};

int even_by_two::_x = 0;

class fix_val
{
public:
    int operator()()
    {
        return 21;
    }
};

template<class T>
struct func
{
    T operator()(T& t1, T& t2)
    {
        if (t2 - t1 == 2)
            return t1;
    }
};
*/
using namespace LeetCode;
using namespace TT;

void DisplayMatrix(const vector<vector<int>>& out) {
    for (int i = 0; i < out.size(); ++i) {
        cout << "第" << i + 1 << "行：";
        for (int j = 0; j < out[i].size(); ++j) {
            if (j == out[i].size() - 1)
                cout << out[i][j] << endl;
            else
                cout << out[i][j] << ",";
        }
    }
}

void DisplayArray(const vector<string>& out) {
    for (auto it : out) {
        cout << it << ",";
    }
    cout << endl;
}

int main()
{
    std::cout << "Hello World!\n";

    vector<int> nums{ 10,5,2,6,100,2 };
    int ret = TT::numSubarrayProductLessThanK(nums, 100);

    //vector<int> ret = TT::findAnagrams("cbaebabacd", "abc");

    //vector<vector<int>> firstList = { {1,3},{5,10} };
    //vector<vector<int>> secondList;
    //vector<vector<int>> ret = TT::intervalIntersection(firstList, secondList);
    //DisplayMatrix(ret);
    //vector<int> nums{ 1,3};
    //int i = TT::search(nums, 3);

    //vector<int> nums{ 0,0,0 };
    //vector<vector<int>> ret = TT::threeSum(nums);

    int iRet = 0;
    iRet = iRet;

    //vector<int> nums{ 1,-2,-3,4 };
    //int ret = TT::getMaxLen(nums);

    //vector<int> arr{ 1,2,4,4,4,4};
    //int ret = TT::containsPattern(arr, 1, 3);

    //string s = "";
    //int ret = TT::countValidWords(s);

    //vector<string> out =  TT::letterCasePermutation("1a2b3c4d");
    //DisplayArray(out);

    //vector<vector<int>> out = TT::combine(5, 3);
    //DisplayMatrix(out);

    //vector<vector<int>> mat = { {0, 0, 0},{0, 1, 0},{1, 1, 1} };
    //TT::updateMatrix(mat);
    //string s = "abcabcbb";
    //TT::lengthOfLongestSubstring(s);

    //vector<int> nums{ 1,2,3,1};
    //int iRet = TT::rob(nums);
    //iRet = iRet;
    //string s1 = "a", s2 = "dcda";
    //bool bRet = TT::checkInclusion(s1, s2);
    

    //NodeT t1(1), t2(2), t3(3), t4(4), t5(5), t6(6), t7(7);
    //t1.left = &t2; t1.right = &t3;
    //t2.left = &t4; t2.right = &t5;
    //t3.left = &t6; t3.right = &t7;
    //TT::connect(&t1);

    //vector<int> vec{ 1,2,3,4,5,6,7 };
    //TT::rotate(vec, 3);

    //Codec code;
    //string ss = "[1,2,null,null,3,4,null,null,5,null,null]";
    //TreeNode *root = code.deserialize(ss);

    //string ss1 = code.serialize(root);
    /*
    MaxQueue que;
    int val = 0;
    val = que.max_value();
    val = que.pop_front();
    val = que.max_value();
    que.push_back(46);
    val = que.max_value();
    val = que.pop_front();
    val = que.max_value();
    val = que.pop_front();
    que.push_back(868);
    val = que.pop_front();
    val = que.pop_front();
    val = que.pop_front();

    que.push_back(525);
    val = que.pop_front();
    val = que.max_value();
    val = que.pop_front(); 
    val = que.max_value();
    que.push_back(123);
    que.push_back(646);
    val = que.max_value();
    que.push_back(229);
    val = que.max_value();
    val = que.max_value();
    val = que.max_value();
    que.push_back(871);
    val = que.pop_front();
    val = que.max_value();
    que.push_back(871);
    val = que.pop_front();
    val = que.max_value();
    que.push_back(285);
    val = que.max_value();
    val = que.max_value();
    val = que.max_value();
    val = que.pop_front();
    que.push_back(45);
    que.push_back(140);
    que.push_back(837);
    que.push_back(545);
    */
    //val = que.push_back(); 
     //   val = que.push_back();
    //val = que.push_back();
    //", "push_back", "push_back", "pop_front", "pop_front", "max_value", "pop_front", "pop_front", "max_value", "push_back", "push_back", "pop_front", "push_back", "push_back", "push_back", "push_back", "pop_front", "max_value", "push_back", "max_value", "max_value", "pop_front", "max_value", "max_value", "max_value", "push_back", "pop_front", "push_back", "pop_front", "max_value", "max_value", "max_value", "push_back", "pop_front", "push_back", "push_back", "push_back", "pop_front", "max_value", "pop_front", "max_value", "max_value", "max_value", "pop_front", "push_back", "pop_front", "push_back", "push_back", "pop_front", "push_back", "pop_front", "push_back", "pop_front", "pop_front", "push_back", "pop_front", "pop_front", "pop_front", "push_back", "push_back", "max_value", "push_back", "pop_front", "push_back", "push_back", "pop_front"]
    //    [], [], [], [], [], [], [561], [237], [], [633], [98], [806], [717], [], [], [186], [], [], [], [], [], [], [268], [], [29], [], [], [], [], [866], [], [239], [3], [850], [], [], [], [], [], [], [], [310], [], [674], [770], [], [525], [], [425], [], [], [720], [], [], [], [373], [411], [], [831], [], [765], [701], []]

    //vector<int> nums{ 1,3,-1,-3,5,3,6,7 };
    //vector<int> ret = TT::maxSlidingWindow(nums, 3);

    //string str = "0-1";
    //int val = TT::strToInt(str);

    //string s =".2e81";
    //bool bRet = TT::isNumber(s);
    int j = 0;
    //vector<int> pushed{ 1,2,3,4,5 };
    //vector<int> popped{ 4,5,3,2,1 };
    //TT::validateStackSequences(pushed, popped);
    //vector<int> nums{ 1396936618, 376963031, 1622631246, 640278640, 539496541, 1973287659, 856013819, 1853361948, 363321932, 458272493, 1794756251, 1240606806, 1169851094, 1673811039, 757372433, 862973450, 1269865314, 1859739146, 2127583276, 1088553864, 243473124, 670741187, 140586696, 1346068058, 2140408751, 1317893932, 1366796264, 9102820, 808201781, 1597468066, 1872531836, 331479057, 1548188785, 1641705584, 299019017, 1877966605, 2086196351, 637984005, 2112668892, 1943170020, 1793341706, 1584121424, 1618021623, 382493078, 1511767774, 1069061786, 1633199358, 1443483909, 1374659657, 748599054, 1912940964, 44006615, 341872522, 1706182101, 215682822, 1510038904, 1268416676, 342073654, 477843186, 1164660148, 76405757, 1051857506, 2080639578, 362720299, 1668138337, 867814407, 81561422, 601309706, 1401655241, 432803527, 1379323576, 426573051, 1948540636, 1960970858, 516723434, 807027288, 1528298541, 363079436, 89055808, 829412931, 904362970, 1618011697, 916465057, 1760498596, 920525920, 1914268056, 1225683451, 1875742954, 1641469872, 1153082341, 1647449930, 338142439, 407735949, 245268044, 1317087339, 1030589043, 1779052057, 1238318561, 414931324, 379991763, 120991963, 1411122864, 1907864361, 1273161542, 1262365446, 914633060, 291271887, 599967314, 279011019, 19676782, 77915597, 1338243986, 1231532567, 1946725185, 1247216347, 432803527, 773073610, 1771943912, 628084195, 856340308, 991950937, 1742045156, 668265354, 446155447, 524169037, 561542830, 150490834, 1942903924, 759994532, 868293872, 932764615, 1203461153, 230382393, 2095995649, 592869471, 582365369, 1044817425, 895118842, 554305881, 842384086, 1666054651, 616511448, 359948522, 34081108, 1378500814, 1100200996, 550503457, 290994914, 616093002, 1026794261, 2167163, 1275567711, 1453060351, 1749947805, 1291907803, 1129964453, 1810416056, 1672550439, 358103497, 1053405982, 716554215, 712672222, 1020163856, 935638289, 573123388, 380193002, 316195952, 988963148, 2126524878, 753829834, 1124492632, 987470597, 169785259, 25172241, 2097727245, 724380218, 928484026, 735624869, 1211226518, 1036750589, 1765871333, 469582913, 1613889932, 281614318, 1434565086, 1144093133, 630870368, 154822930, 1826136669, 432376965, 917554777, 1383946152, 1976424733, 1944671873, 706298499, 1545889762, 457923849, 1356397992, 156175448, 1698216865, 509174426, 1522730136, 1789053940, 1460711161, 1713712401, 1169499557, 957650085, 773073610, 1119899291, 630884912, 1608781954, 1466503212, 1563829362, 1194003972, 2145244822, 2125733307, 2095133043, 1963272614, 1228053553, 1486305037, 242609728, 1555530818, 626395339, 2017387197, 554412069, 1376637413, 1861905415, 1428291487, 989634102, 895948646, 719506395, 447197919, 421986640, 1750703587, 1157008126, 881984270, 1327050637, 1371309940, 998142625, 653535138, 297859951, 1012813727, 1716637928, 771010072, 1614308336, 1840179201, 2037000131, 1981891193, 1546116127, 1672550439, 951195037, 1223111467, 958200475, 140736874, 1385437618, 1879985679, 48409551, 630652619, 134529801, 892582892, 270797725, 313785556, 1148226832, 1722450996, 1434565086, 613683320, 373800981, 662800164, 1318177815, 1332380297, 1728533551, 759994532, 295612140, 1760498596, 2027266245, 790323970, 255131659, 2070784863, 1500032466, 1860627160, 551597867, 217747246, 1959715134, 25018660, 128828335, 1032452336, 719583163, 2015289373, 1199114411, 1323993541, 2048701843, 1463777383, 35694755, 1307552366, 2003272511, 1933152779, 893886641, 582944702, 1483226305, 1878339486, 175598738, 1938001746, 1736295572, 1244387544, 1430637984, 1988764940, 2045644546, 2021995410, 249925290, 1210293707, 284571817, 584575260, 295519412, 1956735510, 1349376117, 467289721, 1387461161, 76329331, 1614308336, 1964048383, 1104356906, 1731396689, 1757902382, 1076913648, 1634019272, 464235269, 640840106, 2009394068, 1556563216, 1215221638, 759147960, 494069859, 713781700, 811260198, 1133509292, 2012524219, 1007068619, 1139648749, 972580270, 567518169, 1598733964, 767893538, 1034668070, 1994783164, 237963787, 1543490814, 1459288635, 44006615, 787207608, 238323671, 540036356, 398977496, 837896186, 1929354053, 890966218, 285276315, 91496837, 1074901997, 1971598373, 2145803262, 372983356, 1155942341, 19676782, 895118842, 1005016916, 35522099, 750826293, 1865170382, 1083265348, 1486997778, 694487695, 1462513507, 657337504, 616203666, 1910787484, 1087075042, 763350414, 1329749727, 1900974837, 1073079793, 1401655241, 1156128924, 70713037, 989088836, 636681142, 677955187, 1868337719, 1811084840, 380749810, 1538150191, 1234076025, 1203461153, 1130154485, 872493006, 1221566986, 1502412774, 59295167, 1273764339, 641375036, 1532107625, 1381055556, 1815777153, 2116951779, 1417286567, 1434633095, 917554777, 1379323576, 736414309, 1087075042, 2085170937, 2111704471, 201445383, 1604376983, 1282005587, 71911935, 1530809038, 1190952023, 746636565, 128916947, 1441139101, 1956665680, 615702125, 571409744, 1528298541, 1318441992, 96817872, 674356474, 1511812945, 142444800, 1149648141, 170568690, 1632349255, 1992732597, 771215411, 1952672227, 1048221074, 2145803262, 1696775122, 1774732562, 773899600, 1642137852, 1013551687, 608080381, 1723117227, 1581270682, 1278445438, 36906986, 187522260, 552078463, 1332399820, 1338243986, 1048317101, 1594316734, 1274630347, 673450766, 447197919, 1232217290, 942189421, 1233057302, 1359705904, 108482691, 2123677207, 1402571036, 1019740571, 78650663, 1032459806, 1583324432, 1171414364, 1305497364, 1285860224, 66525416, 804391823, 1853361948, 1557804904, 1844691597, 1522160281, 1971598373, 314262366, 359750619, 2082097207, 962082753, 536235410, 1018757103, 1838792369, 314983799, 378742434, 1718274188, 2090374510, 645037709, 1904155145, 268970938, 253824192, 34081108, 1607235591, 796357935, 1641469872, 234033724, 1253164140, 992890050, 1259369261, 811077462, 1939646782, 677955187, 1269617585, 590273265, 1981891193, 1093691062, 1831700337, 1518494121, 453148571, 1067819891, 1653561548, 121284735, 1920593, 1445450721, 1190674544, 307330271, 1007437634, 533939972, 2012770895, 1411769457, 600825961, 432580229, 473060738, 2040984959, 1168096225, 1016909170, 924953707, 1530003985, 522438402, 1311087982, 494188454, 582481940, 1772062880, 492040627, 1914610538, 1450623777, 963911031, 77183124, 694628316, 650673972, 1411551369, 1427032563, 824346112, 93158142, 281043528, 19137408, 1157867780, 1878882487, 1691759934, 2096622860, 71014498, 551150972, 1463777383, 1593627485, 1819720171, 1503566013, 1038981691, 1255262133, 1192506494, 669024534, 1894380707, 1703105867, 1171417911, 2112874554, 1034517151, 2103005346, 842721223, 1077497411, 1268209933, 1454898855, 1938001746, 1349376117, 457189095, 1818405338, 1667146980, 1013924037, 617558016, 1294928402, 1826117702, 61949619, 2088353326, 1644544197, 650673972, 1376050426, 1717690867, 1497717682, 2142595036, 239628966, 1750703587, 1890213014, 676137164, 2018107478, 2146379908, 2110637321, 487689085, 901240548, 498941396, 128916947, 494932642, 288339753, 1282708948, 484845269, 1810416056, 1320712771, 825004983, 1075649638, 1790076318, 746636565, 2127436999, 2076257698, 2147110708, 926697640, 924044674, 2085689501, 808465526, 1681487778, 1582329266, 2075534857, 116607368, 1872531836, 539604690, 2113641418, 1453060351, 246349712, 435888132, 1409154107, 1804321259, 306215694, 2134386512, 1193899165, 1806822250, 346103644, 1306445479, 2073966494, 159428104, 1069061786, 1546820945, 11336464, 1248109576, 630884912, 698880388, 736068476, 1157008126, 1278710507, 413012799, 1045682347, 1203503499, 646017396, 565643181, 1213904593, 1260277848, 569161409, 1384723041, 208251788, 171966258, 1608111014, 881230514, 808890012, 523050275, 1089514566, 1293734215, 1499248878, 38606351, 638089950, 863600618, 1079833180, 1870448871, 1056851669, 2143449526, 492082850, 2123677207, 595255670, 991651284, 646021739, 206242713, 2055461820, 582676700, 1187536839, 1844849342, 413012799, 384171436, 51207448, 575028848, 2105838458, 928566610, 1234718744, 487166289, 85587158, 2082543486, 1265741480, 2044556928, 980907223, 1998154290, 991363673, 1281237028, 2044556928, 1332399820, 752669214, 1858982453, 673601219, 1127804894, 946909849, 232647782, 1147491775, 2095995649, 1382497496, 237963787, 864704485, 1668138337, 1859739146, 455432523, 2112990879, 1998154290, 1155942341, 108545779, 1411855029, 1890855407, 771024103, 1188523862, 472338294, 53206536, 71911935, 846179692, 1039595273, 965644161, 811480634, 280491536, 788457811, 1591557509, 719696436, 434541320, 1108936063, 1248785289, 1941758098, 256233144, 687723897, 1231675182, 1884369021, 1909099149, 571409744, 1324682306, 729980114, 1085542797, 121284735, 795788279, 807027288, 1344027472, 1912940964, 1593286454, 467854460, 1554825354, 61028776, 973314056, 1345699992, 888674112, 667353886, 1282005587, 2025874135, 129649389, 2145244822, 1188523862, 1668138337, 1545709767, 1985664276, 1364281340, 37683750, 560583198, 140586696, 480891657, 1365680621, 979361639, 1455684643, 1483328308, 240289951, 316656456, 11381248, 677497477, 1385083534, 44006615, 737186460, 963221857, 1908628929, 2017631802, 3365714, 1946678648, 1999828290, 2127436999, 241561914, 1304872872, 1168778658, 1442878578, 1997099363, 1863000871, 549155083, 1346068058, 1074793835, 757378897, 359983009, 131345167, 1801990879, 916465057, 1689061365, 1183405041, 1828888563, 340162635, 482369170, 1103028140, 1365211750, 2145493341, 801358, 379005158, 233723813, 1124452456, 1973287659, 771995861, 100349633, 508064377, 712672222, 1096020823, 1208633975, 686927609, 633327842, 1613281447, 991651284, 1110076823, 1206296453, 2078928603, 1805797459, 821114813, 606336526, 367714288, 2699240, 480110638, 539966242, 2004343984, 1861694402, 736915210, 1316357157, 932764615, 1976618412, 1390687643, 1696775122, 682243247, 1215221638, 840343146, 2097604982, 705807554, 679486130, 1311915472, 97928048, 1934336201, 452131788, 1914183580, 1030686481, 824422601, 128828335, 1115872421, 847825210, 1675313998, 1850267754, 1147588902, 2068377748, 1199114411, 829380997, 249062960, 1694085834, 345368590, 622048148, 113773003, 1026928318, 1430064941, 753947465, 122182032, 753962400, 1095395801, 1526227772, 2116951779, 73041768, 400787247, 2004228524, 83075013, 52831353, 1333525609, 1663696699, 60023007, 2024257868, 935047258, 964312682, 2127809895, 696089768, 18307937, 1721296419, 1487951762, 777503463, 9396212, 120991963, 618917494, 359783845, 1806822250, 1162358859, 1423560521, 1402455198, 2111157715, 172191416, 827360684, 878106967, 500691908, 447104596, 387231094, 1417013841, 1003141551, 1187536839, 2004228524, 222979092, 2083958022, 963911031, 591266985, 583355361, 36206165, 316103767, 197518916, 256251800, 636696092, 2128135494, 84405079, 982098496, 1069246343, 2088438151, 552168977, 666865620, 763350414, 1923964011, 1315420570, 1103028140, 1231675182, 580675343, 2016607359, 304994218, 675772546, 920525920, 1240606806, 652631357, 1263170135, 560587689, 487166289, 379991763, 272551264, 1735185224, 1584713478, 671522903, 1597468066, 1113598166, 1781613856, 112086657, 573123388, 7421568, 10212836, 1930114840, 223121215, 1588915892, 242590710, 294978747, 2086003977, 633282367, 577466013, 1010928145, 1450028610, 1824785680, 1980106071, 1020352934, 26575566, 1397369881, 1345699992, 1543490814, 558216453, 1075269657, 1452159314, 1356844070, 849139883, 925309338, 1119892765, 815727142, 1218744211, 2142652689, 1530003985, 672467289, 1684381188, 641345496, 1670940672, 1706182101, 885505369, 1148226832, 141900477, 1844853413, 552168977, 1329749727, 894972214, 1774732562, 1790663327, 540680368, 713781700, 1300480914, 427349270, 1364507603, 140736874, 1992732597, 1631393442, 292390521, 519275504, 1376030440, 1672425171, 1908628929, 979687467, 573452969, 1487951762, 1621676102, 143294963, 677504106, 737186460, 1539947824, 731365818, 2040984959, 902842256, 671117865, 324271879, 1088553864, 407288229, 1069061786, 96817872, 2089306052, 2147012933, 1715065571, 961523717, 1939646782, 1075269657, 2087630972, 582910489, 1601986079, 1300128894, 458981757, 54894678, 827360684, 1674290667, 1037616788, 188419003, 401113842, 1475949973, 1284572831, 978628216, 2048604124, 1251373739, 2027896173, 2065585196, 1948540636, 291271887, 1516411974, 1009601766, 359783845, 736042752, 1294928402, 1824785680, 1909262549, 1834791475, 2134524630, 677536938, 539496541, 194264310, 1620418221, 1948540636, 615558721, 2002847941, 1782116234, 159396869, 1774242950, 674768671, 56422677, 530959399, 912740029, 443431060, 1810416056, 992163399, 57555755, 1959440039, 1499698026, 480891657, 936820699, 993356359, 693807790, 67116716, 320041772, 1228612728, 442048367, 771995861, 1311786019, 771010072, 543968257, 1025767564, 1872531836, 523050275, 922602971, 26575566, 61028776, 662103946, 104071768, 730706747, 616593416, 1750460304, 285276315, 968595405, 169785259, 232647782, 2143685121, 170568690, 620932879, 1048221074, 1833291826, 1903627656, 440158160, 1586440579, 948886854, 641419685, 409379426, 1269134895, 1211361461, 461930724, 1945203110, 494932642, 1913013578, 1557849572, 1819720171, 217747246, 2027688546, 21442201, 320539453, 1289387356, 1411585041, 1503331574, 316103767, 373800981, 1808419406, 1475949973, 608696881, 825004983, 849195623, 1651666404, 809686629, 1638450216, 1253164140, 1969414871, 1411769457, 1963272614, 159396869, 673631460, 575641267, 617170470, 1348231040, 61949619, 1188209276, 1530003985, 1045682347, 671522903, 1884811739, 1900974837, 2142652689, 623828341, 1269865314, 1197611032, 724133082, 1318441992, 1600103637, 1100855205, 1406915594, 1831510420, 443431060, 1790522568, 724360342, 1757701636, 428978032, 1781617161, 1564722785, 1971598373, 1396115414, 348439232, 613683320, 1171417911, 1190674544, 1436018378, 387459051, 316103767, 2141155441, 507532484, 2001461158, 1113598166, 1812790817, 1903627656, 2047425499, 1327992199, 641411139, 992163399, 1600103637, 881488639, 333712532, 640232726, 1844853413, 931678638, 417586065, 1527662877, 724748364, 860200500, 732638855, 70124639, 174807551, 414931324, 1273956801, 835560621, 1497717682, 118026439, 901240548, 1852630186, 1234718744, 593199673, 2016651138, 1468805928, 1333525609, 1366951141, 240169153, 2028660000, 2113641418, 1675066569, 1164440511, 508869353, 1365809009, 717486374, 270797725, 169610119, 1706679679, 371031890, 349696042, 1518136367, 1411102047, 377386929, 1398779834, 859413832, 421986640, 176416600, 1323993541, 197339965, 91359694, 836520453, 1795222379, 736712894, 487124508, 1802201929, 677536938, 1723295543, 1244387544, 210101623, 1355330826, 90120712, 469414452, 18859033, 925959346, 1620861656, 995170030, 2048604124, 1713712401, 1581367123, 933528259, 899326350, 1018757103, 1087075042, 1637634637, 1960553676, 1903627656, 1960970858, 1671923928, 112619849, 1857462107, 1426932897, 1240878843, 84757944, 2034758704, 681796983, 601042921, 1582329266, 866740870, 2088381338, 776013422, 851626142, 662800164, 1754981562, 353820494, 258201563, 771215411, 700871881, 230463696, 1413707760, 401113842, 1801990879, 1518136367, 343819379, 1666628509, 1556429477, 180573962, 1264639055, 1155492279, 1011473755, 1381275627, 1046486641, 1036750589, 434967654, 270024481, 1734515375, 429941664, 1432146815, 610180905, 314591, 2113359811, 1067819891, 1835712519, 998279941, 1428518304, 1291493027, 913409696, 536235410, 1884369021, 1422271500, 1536769976, 2112990879, 1990625570, 1811178489, 775942328, 223766969, 976541484, 2013428222, 1311388213, 31095436, 37683750, 522438402, 1452096090, 703886873, 1082688671, 468077147, 1077715703, 1285768271, 1270615592, 1910787484, 398056255, 1790663327, 2084373316, 1031447261, 1434390514, 1402455198, 884820756, 1890855407, 1742161552, 629523564, 1013551687, 2093240823, 1562348552, 164594135, 1510606642, 25493886, 1139307142, 717486374, 1221470109, 1890213014, 179841665, 1779586877, 989088836, 1103316090, 1964091132, 256927400, 1278155451, 945413520, 1652121057, 113220891, 88145971, 1785295043, 815727142, 214619324, 1888801182, 320962708, 1539947824, 159335461, 1167970994, 1223783533, 2144903330, 1668501665, 1528298541, 1667625882, 926697640, 1675669717, 584575260, 1555682882, 1643656184, 334567518, 960439822, 1616943187, 1708520997, 999991566, 2143600882, 565243776, 112086657, 50009535, 1964468412, 1468739619, 1544220721, 1064322042, 725422079, 206395892, 1299131130, 1166071620, 2079933713, 3043733, 2031785407, 1683782359, 605771454, 804500684, 968250182, 1393983330, 1742045156, 1996116400, 1210293707, 816430404, 71356786, 730274240, 785111139, 1918193498, 721212094, 373072722, 1722450996, 1329109980, 641419685, 618572572, 2093008638, 682243247, 1050420607, 1225683451, 1397369881, 1688471765, 96420916, 935047258, 854747143, 1505536675, 1857557708, 1742624200, 2046342720, 1154674584, 430025307, 1290018671, 1278676239, 223121215, 672942133, 1248085525, 1031447261, 2013428222, 1718226263, 1518136367, 1743067321, 446155447, 1924333760, 599327109, 194765507, 1244188176, 73260907, 1613281447, 1257033275, 579329924, 556045216, 238323671, 510267675, 61925360, 500470549, 52583288, 466230576, 752817040, 1938242861, 1186715334, 1090526942, 69190328, 35522099, 1247822739, 1599008760, 2054771717, 46552310, 627508865, 2029787528, 1456695183, 280223358, 2090374510, 1975060060, 929010963, 134272693, 186991157, 549155083, 2137620566, 280282651, 1761753757, 582481940, 331047763, 736712894, 942163484, 448198844, 600825961, 487689085, 584575260, 1307861466, 405789612, 2144704787, 1800770880, 525699712, 1554825354, 766249601, 1537926203, 179841665, 1026048961, 1004094984, 507532484, 1466503212, 1364640347, 694487695, 1357190850, 783573236, 783573236, 33829218, 1591557509, 24229660, 1607235591, 718899752, 302216892, 196598673, 1380820336, 345143437, 1300391206, 1053405982, 302847536, 968250182, 859910326, 1173940918, 1194314226, 325439108, 26575566, 1514627478, 307580735, 1863000871, 2027207358, 1981891193, 2030186208, 1338962743, 706324133, 1724354527, 739721108, 1805790989, 3043733, 640278640, 1512217632, 1190674544, 1234076025, 429348027, 1396884988, 1412221520, 117428582, 129433537, 857396809, 1462513507, 625859553, 83304406, 284571817, 2113924690, 447104596, 1199114411, 2099588246, 1132655726, 159335461, 2075981479, 1079833180, 975600516, 2002847941, 1486305037, 1401177460, 1563829362, 998857403, 1658797403, 565643181, 1207131097, 441802163, 2118039687, 660279180, 387231094, 2016556924, 290815972, 1292070009, 737039158, 2124071937, 890547165, 19120016, 2143343429, 848587950, 989668780, 266357059, 1165050953, 2047921346, 320041772, 1264939330, 745007286, 727549138, 1147593589, 285244004, 376963031, 1603818820, 888278364, 1790166079, 705713167, 1625622533, 500681523, 142564263, 1046209055, 1812790817, 296995426, 2143600882, 1728940556, 2007287390, 113675998, 2089306052, 1173398932, 769482452, 1735004505, 75045521, 1386008831, 1886734761, 467289721, 1647251866, 1851331227, 963597689, 505476331, 1667146980, 1007437634, 315780798, 1078768214, 824346112, 1744878590, 1559213812, 256773240, 1588915892, 958071775, 1372260034, 1633959263, 695079799, 898937614, 92676722, 78714454, 1991002121, 449175565, 1933542284, 1375081504, 590883438, 440098639, 1770405445, 991699344, 2121315996, 1750703587, 1684852678, 2079290811, 595255670, 1641368286, 1527921091, 1496225925, 862213962, 1537789034, 1194003972, 1593627485, 664796600, 634539753, 1248519349, 2080906195, 1155942341, 1259369261, 670449622, 1176968507, 177867297, 385376116, 367714288, 2167163, 1642853097, 716554215, 1434390514, 731471225, 1660360631, 1289387356, 70573173, 818891051, 2083199465, 1571122572, 372983356, 318985923, 908807247, 1120224391, 59295167, 1270842164, 42004903, 747680098, 1611197180, 1609451973, 2038245116, 299945134, 875380348, 662800164, 610722474, 483486458, 1975474557, 2055511346, 1317559830, 1766900287, 1862336190, 1938052547, 902842256, 340162635, 551150972, 1364640347, 1593772889, 808465526, 13423326, 1075273376, 1276215730, 759147960, 295519412, 156175448, 864704485, 246569842, 343444919, 1554825354, 1485811481, 1723588189, 389386693, 348439232, 1908628929, 961750267, 1520307502, 1492074493, 1635134078, 1834365418, 1934336201, 1265741480, 1450623777, 1497717682, 91066072, 2112668892, 1485349566, 1659455525, 1129964453, 721131672, 567640797, 1681961637, 979361639, 1082259680, 303031103, 1265592887, 1802560548, 1757731439, 1144128347, 1127127979, 629343315, 667353886, 1107619873, 1329749727, 247065440, 556045216, 899480896, 1852630186, 1684421755, 2055065655, 908881511, 570773690, 1700899364, 1314381526, 1422563275, 427349270, 1663611101, 2013031958, 1386008831, 1727873231, 2013428222, 71014498, 1846103245, 1410954411, 750241107, 161070481, 1557804904, 111433058, 1428291487, 328680096, 849139883, 653535138, 637984005, 1222867743, 752669214, 852747366, 1419024779, 1933542284, 1372260034, 419303855, 567046810, 899695015, 525699712, 1317087339, 328242555, 389453622, 924953707, 1127804894, 887405876, 1644232819, 2131799330, 566988191, 286328550, 618917494, 886911849, 1222144333, 835682322, 137119997, 1433788673, 1964468412, 809686629, 1514627478, 166050056, 191693591, 185042550, 1454839130, 477247649, 904924639, 2027207358, 1505536675, 1633959263, 808201781, 1088610923, 735685184, 2106029796, 1603993802, 566988191, 43739628, 178119014, 763369512, 507676957, 292487877, 2087630972, 943904633, 377386929, 1398779834, 710371222, 2048976932, 1175630307, 329506721, 1686023893, 1319464401, 1957653175, 730274240, 616511448, 306853686, 1384723041, 196598673, 1561312758, 302216892, 1675669717, 1317559830, 1013924037, 561001559, 2037212982, 1799665758, 1088677400, 19120016, 419486419, 1608246551, 1691729820, 1595297232, 1154266445, 1333827656, 145058805, 187522260, 405256043, 1720734723, 1260277848, 713672901, 1557804904, 681775189, 384171436, 1193228175, 1801313449, 1804014012, 1452100523, 769482452, 1132655726, 1333827656, 1611197180, 524248911, 1303860275, 1673811039, 1077369963, 818960863, 1537926203, 1704598013, 1370686942, 1385441999, 255765972, 276557765, 316656456, 1042331017, 1324752892, 875389639, 2111704471, 140586696, 2079933713, 254332736, 467923590, 500251903, 70713037, 789445017, 1720734723, 574212187, 917686375, 992855575, 888674112, 1379257910, 1034517151, 582676700, 565243776, 1561587874, 1147588902, 136506361, 728091867, 606336526, 70124639, 1879985679, 672467289, 4539986, 1153992036, 1158011920, 1536769976, 1550438867, 457189095, 958071775, 1981297701, 2059482807, 937117295, 973922757, 773939306, 1956099809, 1425586318, 1079833180, 1564000796, 1666054651, 1996993015, 796862440, 608080381, 1304211430, 479609697, 1971864586, 777503463, 1317995768, 170432640, 1811178489, 1074901997, 1439861510, 1283126345, 665681011, 1996993015, 1264639055, 249935548, 854747143, 847825210, 1311087982, 1195083873, 888602298, 1043384720, 691147134, 1795516540, 428247507, 1957653175, 236509131, 788457811, 752817040, 1608111014, 933528259, 1694097056, 1119899291, 1547390000, 1176968507, 1771885870, 1880664588, 1612994450, 1003814176, 1930114840, 939977907, 957417597, 1293398167, 1385437618, 1906071809, 2093240823, 569016291, 1505536675, 1311413985, 2082060481, 272151751, 48522034, 1284572831, 1861694402, 1885850928, 302216892, 1547556451, 199949272, 1966868632, 285024128, 988963148, 2095052868, 2133347896, 1728175502, 1816188605, 634031302, 1987467060, 134529801, 1971864586, 68494243, 54894678, 1147491775, 75045521, 739721108, 554412069, 1344439218, 234192250, 1878277601, 975911080, 569161409, 453007386, 468077147, 1700857774, 859413832, 583355361, 1060947640, 1788735617, 441802163, 1343828193, 1278710507, 2019622393, 46644677, 1387023589, 1204744516, 1221470109, 1737942445, 1865368027, 36906986, 387794786, 1076122222, 1228849520, 2018107478, 1347441462, 2016556924, 2033711141, 2055160246, 416286878, 1250672890, 1115872421, 99712434, 677504106, 1521285637, 576780426, 669024534, 523459333, 1624414188, 484859646, 979687467, 797358681, 1436931100, 752256265, 434967654, 937117295, 89012233, 1539356332, 1427032563, 400658276, 661094088, 630870368, 231848344, 861989552, 560587689, 1342281711, 642036475, 605724786, 1831700337, 181031220, 995490919, 1248109576, 1884200899, 960439822, 1071422160, 2086003977, 2048660941, 811480634, 579822303, 1396899887, 296620453, 1591557509, 1239627543, 106677026, 2086316860, 1426932897, 1869961542, 1813679115, 762361641, 2117831808, 210582579, 1620418221, 574669571, 2085266832, 190352713, 760002861, 407288229, 1427722127, 2086900020, 496016114, 360021262, 1609451973, 387320530, 150860464, 1211038064, 1422563275, 1332785199, 1661239006, 339055560, 1345699992, 528327465, 292487877, 337213357, 1861905415, 1032459806, 1782866195, 1976646642, 849601284, 1396907779, 1008226719, 279376844, 14742310, 1055006562, 743808137, 749641646, 1450028610, 1481833245, 149016291, 1600604675, 7795593, 888852972, 73041768, 1008225498, 555039840, 1905669453, 1379257910, 1396899887, 824422601, 1385441999, 455432523, 532150406, 849195623, 1396115414, 62791287, 1050420607, 811260198, 975175262, 1827417037, 1082688671, 1396936618, 1082907239, 2099588246, 1845370885, 491958987, 573452969, 1348946657, 1856377284, 3043733, 967877199, 2048701843, 560772329, 1952141087, 1482279908, 882326114, 197518916, 359709640, 1661915959, 931387074, 2117980737, 1487951762, 68494243, 307875124, 681775189, 1340977251, 1779829776, 430552662, 88803521, 1243203015, 1855698525, 1385441999, 1728534993, 1073079793, 114312446, 940171623, 495013822, 309933752, 184129929, 1232217290, 804500684, 280282651, 1544220721, 693807790, 671117865, 618572572, 1296133422, 1028101034, 1970698613, 889792282, 1767572375, 1311413985, 1005016916, 1540343346, 728904644, 665770747, 717717048, 1090526942, 1093691062, 1034032416, 944946539, 754005324, 1886819148, 6346180, 2007091187, 580675343, 93465029, 1270222870, 1378967006, 857396809, 430025307, 256663046, 2075980952, 1267636986, 1742161552, 591110565, 870387984, 1354565088, 1969414871, 518814904, 230463696, 2123156216, 1409020242, 1608246551, 936820699, 10686441, 1308077549, 1082259680, 573452969, 789340727, 1322994336, 1557849572, 816430404, 1041748678, 1737942445, 1164660148, 753909491, 1790166079, 1942903924, 1834296774, 1537919837, 18631163, 946909849, 339395771, 866269319, 2111938023, 545368663, 1675066569, 869024197, 924342751, 1765871333, 1460342150, 1119892765, 1192506494, 1446700399, 1288190602, 705807554, 1204432553, 1549166473, 19237053, 1265592887, 2126524878, 1569611228, 19120016, 1628029915, 821114813, 1539938826, 2065585196, 1611706597, 992796140, 1051699659, 2093456594, 572365472, 108545779, 387320530, 1423560521, 582944702, 1813679115, 237735526, 2076257698, 1283254604, 385376116, 67116716, 1087715502, 601309706, 1651268183, 944946539, 1066665267, 1147593589, 893445493, 1541030844, 696089768, 1367500359, 1753989954, 270024481, 809793505, 2141155441, 2100800063, 141077553, 1993316245, 1839290080, 2132253279, 1404358419, 942189421, 1952672227, 1603818820, 1907864361, 684722053, 1248785289, 2074717391, 1518213560, 1546116127, 2083669856, 295519412, 2069771726, 1044817425, 469414452, 1884369021, 881230514, 1153992036, 149736693, 1542896858, 2015289373, 1205245327, 409379426, 1714179101, 1169851094, 1885965404, 160260605, 1363118083, 1543674834, 964312682, 1460711161, 233414883, 1154266445, 906238786, 1419545489, 1940795560, 1781617161, 201890473, 1924532149, 175277739, 82073308, 486954654, 158403416, 915635683, 790323970, 823163860, 1078541512, 1387461161, 528124516, 246349712, 1991147180, 1254641799, 829380997, 411719865, 688614475, 369774785, 914569165, 687723897, 1698216865, 1549965476, 469414452, 442636741, 1988119494, 108919360, 2115076912, 1833291826, 893445493, 9102820, 655887191, 612765355, 2085689501, 432580229, 1529002005, 32789456, 787207608, 677536938, 1845991903, 547513197, 430395950, 914629741, 719844251, 1708194430, 1147385247, 1325056774, 1087715502, 1273764339, 1689415715, 13802668, 1850169472, 1626068947, 563563642, 764948555, 1494675360, 2070432557, 1118085381, 472354443, 2081400687, 1491775538, 1609459107, 732360464, 1805797459, 113675998, 1173940918, 763369512, 811077462, 672942133, 1532102703, 852747366, 794089417, 886911849, 431401920, 448600121, 1616943187, 761314755, 184129929, 1256600986, 440720713, 813114273, 824346112, 149924982, 1611706597, 1672176514, 1402455198, 1258575394, 1646813814, 881984270, 1850541963, 727290358, 1423560521, 920286748, 516597192, 1561312758, 571409744, 945413520, 1175630307, 2033711141, 1310925515, 35694755, 956607105, 623816090, 161070481, 608861700, 1020163856, 1264706694, 440158160, 400787247, 568638780, 1365809009, 496016114, 2068537336, 614013617, 715251833, 1355330826, 169852557, 922426422, 1790522568, 2143685121, 362918215, 868293872, 916465057, 1294928402, 1275567711, 52831353, 1608859846, 499681507, 1459288635, 1591465824, 1826117702, 227303008, 1663611101, 1498850799, 1450028610, 915974138, 717609417, 732572932, 1468921066, 502112347, 1940795560, 1744930556, 958200475, 1436018745, 652631357, 189133073, 469582913, 1486997778, 724748364, 646017396, 1954893475, 2083199465, 2020646568, 1292070009, 637984005, 1118590297, 1258575394, 
    //    2069940451, 10212836, 1689061365, 2128135494, 1663696699, 180663141, 527762521, 1756558241, 1647449930, 519275504, 1802932458, 2087630972, 1380820336, 420878795, 1786108570, 672467289, 1325477525, 2110637321, 25167384, 1347441462, 281196812, 834909679, 684722053, 666865620, 237735526, 197518916, 1367500359, 568638780, 2034932223, 1976646642, 399741236, 1708029154, 280223358, 867814407, 1468921066, 1402531066, 1914067899, 879720775, 1992732597, 1211216203, 1844849342, 1563320665, 389386693, 808890012, 948886854, 1314381526, 51207448, 329506721, 895948646, 286328550, 1908998721, 1972392443, 2128082016, 1742624200, 928484026, 620623299, 639803614, 448600121, 240169153, 21442201, 1843066414, 1307861466, 1505389493, 869492957, 1043384720, 1945051621, 1728940556, 95898038, 957650085, 62714432, 387794786, 1002798106, 2071436105, 140421808, 216088210, 508500145, 1424830064, 406201474, 608861700, 221013942, 334598901, 452131788, 1293734215, 686196847, 1206680576, 123262014, 788457811, 1249030677, 1910787484, 70297915, 942165348, 1800770880, 1615138117, 737186460, 922602971, 1370686942, 1427628789, 1379758814, 1729190501, 362918215, 992796140, 169417523, 315780798, 297949086, 1499248878, 700429215, 291271887, 1512251088, 2111938023, 232765397, 266541344, 326524541, 1485349566, 160630711, 959287618, 1643656184, 836520453, 1976618412, 1672550439, 1303434357, 1468739619, 1982380599, 1936745197, 1195083873, 122182032, 1124295893, 1660502484, 1542896858, 1077497411, 582477025, 557831566, 870944318, 1069246343, 1769456284, 1399558106, 1435707183, 1934803291, 2732847, 418226586, 351796145, 1302743503, 1801990879, 1596807024, 1008414920, 382493078, 1402531066, 36206165, 668090206, 694840627, 1806988813, 169785259, 890966218, 1757731439, 1735844665, 1228612728, 2111157715, 1806274867, 279200661, 208251788, 595750919, 1530809038, 1078768214, 645037709, 719233939, 1326546568, 1609380119, 772347915, 1835543376, 978266798, 957417597, 1649751675, 681290040, 500691908, 317328226, 2127581327, 266541344, 30049307, 568669708, 1281036306, 138942590, 1292021335, 1475949973, 785111139, 972580270, 1569611228, 732360464, 915955964, 1716637928, 1072335882, 1332399820, 313785556, 857345196, 1904415891, 1732556898, 1957033790, 473060738, 1184638371, 1952141087, 1524665614, 26100274, 965644161, 142109411, 2123916736, 600977316, 1290018671, 1821959069, 1555530818, 1707471039, 1343540831, 123828, 2016651138, 255765972, 233723813, 418226586, 1324345778, 299675870, 1230641096, 1761896418, 1675226280, 827875919, 1842157899, 991749800, 924342751, 119437024, 78714454, 921819989, 424696730, 1516411974, 398734164, 493084626, 2141313080, 1361437771, 943904633, 1550482403, 113141376, 1576441802, 921819989, 1734287064, 1939584521, 1059503901, 1597162990, 1564722785, 2086316860, 1743067321, 2017631802, 841509146, 1944566459, 616912329, 1723588189, 745862339, 1227916061, 1376637413, 233723813, 1263723060, 694628316, 1059503901, 242590710, 970558419, 1949096656, 187522260, 297540100, 1923540173, 829412931, 993356359, 222457627, 616593416, 1139307142, 707579938, 190352713, 603313453, 240922878, 1124295893, 1471137299, 1699441673, 1303434357, 400787247, 1235720890, 1654635758, 1303860275, 574212187, 409281076, 1562348552, 1634019272, 639517117, 1434633095, 1357895568, 2012524219, 2050618997, 89055808, 1761896418, 764235441, 1721296419, 1586440579, 753829834, 1302743503, 376963031, 1317995768, 1395884151, 1385083534, 1903908334, 1976646642, 1522730136, 38606351, 349696042, 1516821127, 247065440, 1651268183, 281043528, 2144903330, 180573962, 314262366, 1326546568, 1663696699, 858829717, 539491282, 91359694, 542198534, 196422769, 2074085640, 701948913, 500470549, 1779586877, 641525347, 924044674, 178119014, 2020646568, 2047921346, 139599021, 727744736, 281614318, 305646046, 506184654, 871325053, 975569011, 719233939, 1536860934, 1923964011, 603388061, 1218744211, 937135406, 1338087899, 1614308336, 1600628410, 1545709767, 1118450555, 880522474, 2009466687, 480110638, 815727142, 1815777153, 1473175110, 1130154485, 1774242950, 470048799, 1217080259, 1124945499, 609886646, 1050420607, 297859951, 1475074700, 810986047, 1005016916, 446159266, 1381275627, 310702305, 1785904403, 328804905, 1760498596, 1143676418, 334567518, 362720299, 96420916, 1276871085, 598655629, 915955964, 729980114, 1957033790, 1479529708, 463494602, 600977316, 1797295700, 929010963, 1730690043, 921817678, 889200557, 1804686773, 1743067321, 1622955755, 1248085525, 2111157715, 1712007017, 158251385, 292974750, 69190328, 2090523966, 1676356044, 295491359, 657978301, 184792528, 1564000796, 1658573207, 738467374, 1324682306, 1717918563, 1812790817, 622048148, 2049474593, 1886654115, 1215221638, 201126863, 1012773338, 848545917, 1801313449, 686196847, 500134357, 1557849572, 1608246551, 234033724, 739483285, 507676957, 508869353, 1229158282, 24859467, 1555682882, 63037272, 1644232819, 173182251, 1443483909, 34673913, 2066837724, 214736090, 1708003222, 428338322, 1604806597, 1132655726, 1554624323, 623816090, 1075229520, 294055099, 1952404090, 1666286463, 1548188785, 1438349914, 770280710, 66659843, 1434390514, 84092947, 1043514166, 2071436105, 1729550368, 1956665680, 535399523, 1595297232, 629523564, 646021739, 1238318561, 965644161, 497156672, 1254919095, 958200475, 521517401, 1936745197, 2137089434, 1186715334, 2112874554, 565643181, 1309029058, 1071836509, 1632958186, 122130473, 1020163856, 129909114, 1755643328, 471578550, 2120954882, 975600516, 194765507, 1728087461, 506184654, 160740908, 1991147180, 2100334854, 2097887691, 1124492632, 1125568125, 1560956680, 1443349587, 1453060351, 962654654, 333825440, 1092046035, 1515893503, 1411856781, 2096622860, 1785904403, 196422769, 201979455, 1494675360, 2141155441, 262134483, 1949096656, 621776839, 496016114, 2081373870, 438726876, 630884912, 322876067, 867814407, 975569011, 1327992199, 2112874554, 606807065, 2023692229, 829844668, 166636431, 1607302145, 303155937, 1160418779, 547513197, 1609459107, 277315685, 1609380119, 2055160246, 2082060481, 247274314, 1659934711, 524697654, 356817122, 1785295043, 1802560548, 826110622, 790151726, 2023856660, 2068377748, 122130473, 307073627, 1882458523, 872963203, 1157867780, 1943170020, 1387023589, 2083958022, 1340045982, 1396899887, 2027896173, 1085765563, 1998154290, 831283442, 1247216347, 1303796069, 1207213487, 640898418, 915974138, 1920593, 1879985679, 1783466941, 1609451973, 1224228173, 1620861656, 508500145, 1214336263, 1048135095, 424893895, 1011217885, 995170030, 1248519349, 1736295572, 2056381598, 652631357, 1531220755, 514902004, 13423326, 123828, 1238093883, 1954714276, 1296327936, 1221213295, 771024103, 255765972, 1728534993, 874059158, 1278445438, 1324752892, 838119681, 858267769, 586645833, 566988191, 450341313, 1282005587, 1253164140, 1557848530, 1308068086, 215682822, 299675870, 295612140, 1628029915, 860200500, 509174426, 716470693, 681327017, 627508865, 1615138117, 2146379908, 214825164, 1577120247, 1922585086, 898937614, 835560621, 617719969, 1686023893, 1399558106, 1393568723, 1795634167, 735685184, 517530367, 1284372870, 1463567802, 1850169472, 1300480914, 1463183151, 62714432, 1214336263, 24229660, 1816566071, 1384091771, 691079513, 1057603270, 780479715, 1085542797, 1165788209, 1729190501, 532299899, 1960553676, 314983799, 694840627, 70124639, 539604690, 1246165376, 1679105630, 850405168, 1045682347, 1584702197, 885127795, 1926927134, 1147769467, 1460342150, 629343315, 1159613901, 1365809009, 1438349914, 89578559, 1600373394, 904362970, 716554215, 595383327, 787207608, 389161685, 551150972, 506409043, 7795593, 1671147232, 1727873231, 256927400, 94588189, 1396115414, 1482279908, 1340703404, 657447605, 279011019, 598312960, 177867297, 399606167, 111433058, 1171414364, 1357999123, 621076266, 1970275095, 1812691524, 1071836509, 2012770895, 810986047, 1386056278, 1658573207, 141077553, 1744878590, 1427499379, 214736090, 2048976932, 747322107, 1797937840, 342073654, 718194044, 1966868632, 689991231, 127197577, 1931582241, 162969804, 1553144697, 862973450, 253824192, 2023856660, 1650535552, 1602437445, 302847536, 1327589513, 1031447261, 697752408, 359750619, 99473265, 1205245327, 1402405454, 348439232, 1130972654, 249935548, 1269134895, 1420926612, 2131799330, 850405168, 1402405454, 279200661, 1609380119, 1404358419, 703886873, 323147739, 1100855205, 1151338385, 384508174, 914629741, 310378483, 85954495, 1625622533, 1231005351, 1818087300, 608920218, 1035691664, 195363835, 246569842, 908881511, 651673594, 735685184, 480891657, 1074901043, 1904155145, 1584702197, 1357895568, 590629426, 1068212119, 1269783183, 2096622860, 183749459, 1413045513, 360021262, 1545889762, 1124492632, 1644674512, 1175573678, 2137089434, 1449275702, 718899752, 717486374, 1827417037, 591110565, 616593416, 1007068619, 1363182895, 2081705546, 1265510028, 2100248276, 550503457, 1587174009, 1835712519, 1429190438, 1953534753, 1302743503, 1750460304, 1273956801, 1607302145, 1475074700, 630870368, 719530340, 778533345, 2069940451, 893886641, 2069940451, 217747246, 140421808, 1435504072, 2019622393, 745007286, 1834791475, 1458040154, 1589400660, 2100334854, 1444730562, 405256354, 1552755694, 1946725185, 565243776, 1104356906, 1158011920, 1684194395, 78209718, 1857780184, 1248085525, 158251385, 1666459717, 576533870, 291984552, 1305803021, 1363182895, 915955964, 1994783164, 1815263816, 1814351551, 1158359413, 1059503901, 1573443332, 605771454, 409574421, 956235134, 1641705584, 803146391, 970479397, 880522474, 973922757, 842721223, 1794756251, 1221213295, 1982380599, 1666054651, 937135406, 1971040710, 1480107778, 1808693192, 525699712, 674768671, 777653239, 1686843282, 1682279037, 199949272, 2130853680, 51942689, 685907872, 111040003, 303155937, 1135568167, 129909114, 857345196, 2002145065, 1831700337, 551276231, 171966258, 417556424, 998279941, 1571852620, 2139999934, 1201149043, 1516411974, 563563642, 1734515375, 1806545999, 1080067, 1934803291, 1768039834, 2119617991, 2142595036, 2081400687, 1514427983, 135052210, 1797295700, 1095395801, 337208013, 1376953390, 1971040710, 500134357, 405256043, 1861694402, 1366796264, 1153082341, 1686843282, 735401071, 2073966494, 1327050637, 112619849, 1936596865, 490333082, 661094088, 1152274190, 1082907239, 2007287390, 1203503499, 304668660, 939977907, 2003207683, 919484816, 642533712, 1704669716, 1714986751, 1240878843, 1049578106, 10212836, 1080438979, 556045216, 560583198, 1223111467, 1003814176, 464498110, 1822671887, 445946453, 1816188605, 1905457709, 247065440, 724360342, 1694085834, 1652121057, 789445017, 1802201929, 419793410, 857345196, 2048976932, 752987405, 1248293543, 216088210, 2106029796, 1814364317, 285244004, 1232217290, 1443702350, 1551803911, 66525416, 48652706, 1508283478, 1311580879, 1003141551, 2027688546, 74226018, 1806988813, 1510038904, 1790522568, 1139098337, 1524665614, 634539753, 1227916061, 997266633, 1188528596, 1665245194, 942189421, 1261433119, 388946128, 1725275294, 1235575155, 1149648141, 184785149, 49604905, 523245686, 1155492279, 417556424, 992890050, 2087786971, 825004983, 1039595273, 1436018378, 440720713, 1278676239, 689991231, 1945203110, 968595405, 1124767833, 1047353326, 1910799299, 1510606642, 303031103, 1864651677, 1420926612, 1800875007, 1008414920, 194264310, 1818405338, 577143729, 1943170020, 696089768, 991699344, 1062998149, 2090897212, 1309029058, 735624869, 156175448, 1385083534, 2060724858, 676137164, 1293734215, 2141313080, 976302754, 1785295043, 1945408679, 2031785407, 1235720890, 894972214, 1390687643, 1681961637, 323243085, 1136748142, 1865372880, 735100554, 1496918515, 1551803911, 1806274867, 2083002453, 1438032980, 740896097, 1025803124, 1181300623, 2113924690, 532150406, 145985700, 1964610457, 1463567802, 313785556, 1611060339, 1326691107, 960439822, 1868337719, 26100274, 759994532, 1944566459, 1393568723, 622671468, 1602079663, 808890012, 3365714, 1771885870, 593372864, 667353886, 735836075, 18631163, 741462593, 357446090, 880201954, 1325477525, 1735915671, 970558419, 1661239006, 650306001, 46644677, 23114128, 769482452, 340162635, 1152011317, 48409551, 1939698, 610180905, 307298640, 92630830, 1154674584, 297800446, 1411585041, 1804014012, 1152011317, 1479529708, 273379488, 728091867, 835320212, 1468921066, 1296327936, 201445383, 2046662204, 468820279, 1311087982, 319317113, 1141992919, 1404358419, 931387074, 1427032563, 1650535552, 1674200383, 1539938826, 48652706, 1554754851, 1311580879, 609886646, 912299042, 689107975, 1755481145, 1529002005, 1264298557, 1303448950, 736970774, 483636114, 63037272, 944946539, 445946453, 563289155, 83075013, 1514627478, 1211216203, 168610581, 91496837, 31749423, 2732847, 775512745, 104071768, 1793099888, 1378500814, 598312960, 99712434, 1828157509, 1945408679, 1452096090, 1887076741, 1019740571, 100349633, 608861700, 91066072, 1791178392, 1141289255, 280491536, 1674290667, 424893895, 1431405251, 1954714276, 210101623, 1080265295, 575641267, 950756568, 74793912, 1028101034, 752256265, 975569011, 94705270, 821907359, 835661314, 469582913, 719506395, 1320712771, 992163399, 440720713, 1880664588, 1884811739, 1523987634, 2090523966, 191917175, 127197577, 1121864383, 434541320, 1622013249, 497709030, 199382152, 1050205021, 999904254, 673601219, 1618011697, 1450968061, 89055808, 19730478, 399955743, 1428291487, 320072214, 719583163, 1731554158, 1020352934, 726913652, 1839290080, 1974306612, 1976424733, 272151751, 2017387197, 2129184081, 184792528, 519488348, 2147110708, 2001461158, 700871881, 430552662, 1631455253, 2083002453, 1247822739, 1412221520, 1797295700, 1193434274, 797216509, 1908998721, 775512745, 1181231251, 123828, 124247141, 911480049, 1744878590, 616093002, 1324682306, 731365818, 715251833, 450341313, 372226306, 381024644, 1852630186, 2043668064, 671543353, 1731396689, 943232983, 467854460, 234000828, 1338303831, 2130785565, 665770747, 114547009, 729980114, 688614475, 1688738109, 1325056774, 334598901, 2034438403, 2087786971, 1345569254, 48522034, 1521285637, 1434565086, 914633060, 399741236, 1728533551, 184129929, 201848154, 900688240, 1463183151, 1255262133, 1010428964, 306500776, 1622013249, 2034932223, 450163221, 1222867743, 1844851837, 673635802, 731471225, 976302754, 328680096, 722974384, 1210372200, 1818405338, 623828341, 747322107, 1098192223, 1357391752, 314262366, 13802668, 446867388, 2029787528, 2013031958, 725422079, 1485671329, 1541030844, 1549965476, 73041768, 256251800, 1838792369, 472354443, 1396907779, 828343957, 2127581327, 2034438403, 539604690, 973314056, 429348027, 2012524219, 1591465824, 752987405, 1001064628, 1131099352, 2037212982, 1359705904, 306500776, 1477785817, 1677309560, 869492957, 523050275, 2037212982, 967913121, 964312682, 1996116400, 1152339406, 999991566, 1556405980, 227303008, 261448822, 942165348, 999904254, 1659455525, 1834316462, 1731554158, 982098496, 818891051, 558216453, 492648842, 1303860275, 258452072, 307875124, 1168778658, 276557765, 1845370885, 991950937, 417586065, 1720623212, 89354251, 118420760, 2093008638, 727549138, 975911080, 1622955755, 117428582, 1905669453, 492040627, 576533870, 1768039834, 769627492, 290815972, 1014111406, 1682931673, 497156672, 1143676418, 270797725, 1956665680, 63965140, 299019017, 1118450555, 1356397992, 689991231, 267831207, 773939306, 201979455, 1030686481, 1859078996, 1637634637, 599327109, 991363673, 74793912, 61925360, 1574120907, 1276215730, 57555755, 1556405980, 1271184549, 342073654, 789340727, 1080265295, 254332736, 911480049, 442048367, 227303008, 195363835, 1268416676, 2055065655, 1938052547, 533939972, 803115772, 1051857506, 1175464638, 381024644, 587320041, 266357059, 31095436, 1111794337, 20954011, 930986510, 1608244402, 547464822, 1952827627, 1108373797, 329314546, 1374659657, 1210372200, 641345496, 384952692, 1149648141, 1804686773, 894972214, 989088836, 568638780, 912365222, 618917494, 1075273376, 870387984, 71356786, 899695015, 1082259680, 6346180, 740896097, 2086196351, 64367067, 579822303, 1426932897, 184785149, 56422677, 737991175, 34673913, 1235575155, 151109077, 540851265, 1767572375, 691147134, 1307552366, 322876067, 1708003222, 281614318, 1866277049, 457923849, 1027152232, 959287618, 1410954411, 1236862663, 1011473755, 880309423, 567640797, 1924532149, 74231091, 177821874, 784195479, 179945569, 1509300510, 1224399896, 319317113, 532543921, 1526227772, 2068537336, 1027152232, 234839644, 945846833, 636912232, 2147110708, 976379823, 2009394068, 1470048459, 88290438, 2025387179, 271360703, 1395884151, 707579938, 492648842, 2086196351, 1782866195, 1063970512, 1600604675, 1139648749, 1071422160, 376564302, 450341313, 602311771, 1850267754, 1822671887, 1582329266, 202564793, 1556563216, 1972392443, 134168194, 1403649304, 359948522, 1975949253, 1092046035, 2106930724, 878106967, 94705270, 582910489, 527911378, 1581270682, 492040627, 767893538, 1264350721, 866740870, 856013819, 1906923326, 788276282, 1626068947, 482273390, 1108373797, 1147385247, 1556429477, 640232726, 17498921, 197339965, 1357190850, 1305497364, 1263298755, 64367067, 399591481, 2018107478, 131345167, 976379823, 1863000871, 343229265, 1361437771, 889200557, 1323152131, 409379426, 1221566986, 141077553, 2048896011, 429941664, 1173940918, 1647449930, 418542232, 524697654, 1699441673, 1940795560, 2076257698, 358103497, 1603993802, 651673594, 70154193, 1411551369, 1326691107, 2039905320, 411538627, 1252058211, 1698757835, 1396455995, 1511679135, 525595959, 841618321, 893445493, 1790663327, 610722474, 176416600, 286777909, 1791805686, 718296482, 31749423, 1456846153, 411538627, 1124452456, 538369511, 86564517, 1364640347, 2072190634, 1119899291, 1046209055, 1988764940, 368910908, 1960621549, 985865213, 725422079, 1088610923, 1271900685, 539491282, 2125733307, 1665297998, 829939889, 2137570257, 61028776, 1543674834, 1672978605, 677661848, 1257274582, 1311388213, 1050205021, 2006878901, 1288190602, 2060724858, 1561587874, 609886646, 1666459717, 1858982453, 249925290, 166636431, 123262014, 1576441802, 989668780, 842384086, 2066837724, 186991157, 509715204, 1691729820, 312683054, 1276215730, 203560754, 1539223058, 2071436105, 595750919, 1161683416, 331555829, 732417423, 1924333760, 372226306, 1064833324, 359983009, 1512251088, 1671923928, 1767853591, 1581270682, 872493006, 399955743, 754005324, 579329924, 491958987, 1080438979, 1888801182, 1503566013, 1387859176, 1688738109, 1274630347, 1380894137, 295612140, 1507259953, 1278155451, 1325342998, 736414309, 88290438, 745007286, 685907872, 1365711003, 1926927134, 1222988020, 1579661247, 83012416, 2091897626, 407288229, 466230576, 1835712519, 1310925515, 2038039768, 948980666, 1393568723, 975010270, 133687821, 492082850, 885505369, 1201149043, 2097887691, 851626142, 1409020242, 464235269, 1439861510, 985865213, 906238786, 159428104, 1365680621, 407154938, 1205980414, 273086001, 1985664276, 992796140, 1241776351, 472338294, 1250672890, 1534316369, 1909099149, 1048221074, 570773690, 1922585086, 1636672122, 412569264, 705713167, 722974384, 439778475, 425279855, 657337504, 1587174009, 1450968061, 1267636986, 1485671329, 440231801, 1465834955, 1147769467, 1527921091, 1918193498, 2075534857, 1192506494, 1198593322, 1269134895, 1960554950, 151102356, 101982632, 500251903, 428338322, 812952582, 710371222, 1628029915, 589352278, 701948913, 223005764, 1117033075, 1701794432, 2134386512, 195363835, 1887076741, 1641705584, 1269865314, 914569165, 160260605, 2086900020, 868065801, 1138603746, 134272693, 913409696, 2145493341, 942163484, 939520654, 492648842, 794089417, 2055511346, 491958987, 818960863, 299019017, 956607105, 1684194395, 766786608, 705713167, 577466013, 1051699659, 1885965404, 1703105867, 561542830, 1674200383, 1481833245, 1366796264, 1774242950, 1741218797, 2024257868, 1846103245, 56422677, 1539223058, 555039840, 1458040154, 142564263, 890547165, 1394172341, 1449961287, 1988411269, 1334034467, 234839644, 241561914, 635003451, 1362476595, 1463777383, 1725552225, 1635134078, 624545635, 2140408751, 1343151144, 1851576207, 1393691518, 1141992919, 751161505, 1136748142, 1713471852, 2123153915, 959837073, 1682931673, 1137211517, 1384091771, 1436018745, 386054492, 2058624704, 2046662204, 1463708231, 1573657704, 239807843, 711842369, 1624414188, 2000372644, 80852967, 894874961, 1396626111, 912365222, 1616943187, 1364342951, 781251781, 1684194395, 527762521, 968946055, 926096033, 4539986, 1190952023, 1982380599, 1636291553, 978628216, 505476331, 302904351, 1749947805, 372983356, 931387074, 398734164, 5768885, 285244004, 1659455525, 1411102047, 593450337, 753829834, 474993201, 1724354527, 1672176514, 1431652882, 145919859, 1349888499, 1364507603, 1791178392, 30049307, 700429215, 655887191, 5561448, 1299131130, 998857403, 951380020, 199022292, 939097123, 968595405, 1460711161, 324979793, 505476331, 1725275294, 1412133344, 1815777153, 318985923, 1658797403, 398734164, 314983799, 1805790989, 299945134, 719233939, 409789802, 294055099, 537077189, 700871881, 1349411090, 1875189672, 1008225498, 686927609, 1154266445, 1383946152, 1165788209, 259034488, 297800446, 1465071702, 1218744211, 424893895, 1043354926, 254332736, 643884630, 961750267, 976541484, 1742161552, 1025767564, 663098336, 240169153, 1481833245, 1586440579, 560059120, 694628316, 1649751675, 1700857774, 1579703639, 579822303, 989287744, 1618878465, 5561448, 85954495, 1351394610, 1552755694, 640898418, 1124295893, 1452755824, 1548188785, 256233144, 279011019, 539966242, 1891724238, 1602079663, 281196812, 2093008638, 412794617, 1811178489, 658422407, 961523717, 1324345778, 870387984, 279376844, 2016556924, 606807065, 1875742954, 1817518320, 532061936, 739721108, 757372433, 397642685, 672975457, 1879999058, 885505369, 1195083873, 1561312758, 1261481503, 670449622, 2082097207, 1208296014, 2144704787, 1238652484, 1095687519, 1401177460, 764948555, 262134483, 1577120247, 918433206, 170432640, 1977288849, 472797321, 796033879, 381024644, 1317559830, 1643983800, 717609417, 69190328, 1008226719, 294380890, 795800901, 902842256, 231798475, 80852967, 2030904675, 1130154485, 1139098337, 986703790, 477247649, 1636291553, 1118085381, 657447605, 1338303831, 1043514166, 1769258509, 1095395801, 1253143944, 135052210, 1864651677, 314591, 591266985, 2105838458, 575028848, 1884811739, 1802560548, 1365680621, 1210372200, 1380820336, 1909104176, 1698757835, 1077497411, 1035691664, 2123916736, 673601219, 1411855029, 797358681, 797632039, 183749459, 176416600, 863600618, 1130972654, 1795634167, 178119014, 1704598013, 868293872, 1618011697, 796033879, 17911512, 1381055556, 1016796780, 251272629, 1564722785, 1593286454, 1684421755, 1574120907, 1778926339, 1671433217, 1865372880, 341872522, 1317893932, 1293398167, 1141289255, 1010234722, 749641646, 256663046, 83012416, 1870448871, 754929893, 2009466687, 1828742743, 20893955, 315631798, 937117295, 477843186, 1755643328, 1100200996, 1815263816, 2024620261, 773899600, 812952582, 1654635758, 1483226305, 1441139101, 1665467551, 83304406, 1636672122, 572175780, 685470560, 446867388, 1265592887, 1845370885, 1460365676, 303155937, 673631460, 147913269, 1038981691, 5768885, 382493078, 1296327936, 1718226263, 167440201, 502112347, 1317893932, 1291211056, 1204744516, 19237053, 269751562, 19137408, 676137164, 2120954882, 199949272, 25172241, 805499097, 258122431, 90549767, 1750874168, 1048758132, 1613889932, 1694097056, 1368196138, 641345496, 1960621549, 136105816, 616934102, 1534316369, 1766266922, 1227916061, 294380890, 641525347, 1231675182, 1880664588, 846179692, 1346068058, 74848147, 1499248878, 1529002005, 356817122, 234185967, 679486130, 839897378, 139599021, 380349092, 770280710, 2138215875, 590273265, 1975704947, 1425586318, 1750190831, 1519114125, 1612994450, 640840106, 494932642, 1076122222, 140421808, 2095052868, 1010234722, 1153396558, 25018660, 1625622533, 452860596, 24229660, 185042550, 1795516540, 1394172341, 1675226280, 199022292, 747559042, 735401071, 1043354926, 99473265, 1856377284, 1798982230, 1976424733, 540680368, 618428739, 1728175502, 11381248, 1127127979, 145919859, 724380218, 725527492, 912740029, 240545952, 569016291, 950756568, 1734287064, 668265354, 1225009754, 614013617, 104071768, 797358681, 2010126824, 1500032466, 1267636986, 1942903924, 1799154706, 1244188176, 2027207358, 616942027, 1201702211, 635003451, 1168778658, 1002798106, 1107619873, 2137620566, 1643061339, 123104157, 1956735510, 2138215875, 1519114125, 417556424, 751161505, 746636565, 1611060339, 994729639, 735624869, 1456695183, 1628918914, 1452159314, 894867366, 1027152232, 704841048, 2133572510, 872493006, 339395771, 749323567, 1007928477, 1444730562, 1411551369, 1600604675, 1231532567, 1064833324, 516449724, 17498921, 1019740571, 1944671873, 521517401, 1483662604, 881984270, 2017631802, 191693591, 777503463, 773939306, 2003207683, 1703120002, 863714478, 487166289, 1750226398, 1278676239, 258613640, 141900477, 123104157, 826120529, 921817678, 675772546, 1254377714, 7421568, 177821874, 279138325, 508064377, 2017618050, 1260277848, 1860627160, 37139523, 1713471852, 1077369963, 1781613856, 1642137852, 135052210, 1164440511, 80129317, 1985664276, 1826117702, 513084761, 1587354907, 2048660941, 670741187, 1949096656, 1094065633, 48652706, 510267675, 1746167885, 1728087461, 721212094, 2088353326, 1141984247, 188356918, 1359245518, 1282233723, 688614475, 147531315, 1778926339, 208251788, 924953707, 303661871, 1445450721, 309933752, 191275689, 1641368286, 201848154, 1307861466, 71465821, 292487877, 1212355580, 2100248276, 681796983, 922602971, 1844851837, 1462230070, 801723862, 737039158, 1009601766, 1342784702, 1349386537, 1402405454, 1735004505, 128916947, 2055461820, 2075980952, 1483813177, 924044674, 2019622393, 1524611285, 1532107625, 1406915594, 1604627318, 636696092, 850439096, 258613640, 1211361461, 2111938023, 1025803124, 1976524983, 2127809895, 1931582241, 1381265949, 421986640, 153378523, 1268209933, 13423326, 17911512, 657978301, 413012799, 816811738, 665681011, 549074999, 30486725, 1714986751, 912299042, 287193693, 1814364317, 187309166, 1433067572, 329314546, 108919360, 567046810, 572365472, 298037935, 1723295543, 809793505, 1670940672, 605771454, 1268209933, 542986325, 1723588189, 757372433, 201055019, 428338322, 1204432553, 1519438783, 1230641096, 2004343984, 1300480914, 1952827627, 1818087300, 1862294135, 1010010937, 859549329, 672352493, 96817872, 89578559, 1193899165, 453007386, 1019066051, 1969414871, 1675313998, 1158359413, 694256689, 2047921346, 1156128924, 605724786, 776013422, 685907872, 740739813, 854672462, 1682931673, 930986510, 1214336263, 201126863, 552078463, 1573657704, 920525920, 1531220755, 2142652689, 686702452, 147913269, 1644544197, 2047566941, 1355858926, 903572390, 136506361, 206395892, 724380218, 747322107, 483486458, 1090499079, 998142625, 859910326, 739483285, 94588189, 1916913646, 21182638, 1865504928, 2139999934, 1074901043, 915273719, 1846103245, 2034438403, 149924982, 1744274428, 963597689, 1013924037, 335001283, 307073627, 1381055556, 681290040, 563289155, 757378897, 297949086, 915273719, 1688515393, 1508578080, 306500776, 1969222382, 909436300, 2067470101, 1545669143, 1468805928, 516723434, 672975457, 1442585080, 1910799299, 1262225938, 1987467060, 1088677400, 1255262133, 19237053, 801358, 430025307, 4539986, 160740908, 1951271101, 153378523, 569161409, 1268416676, 822686065, 1213904593, 516723434, 1988119494, 823163860, 1832669442, 400658276, 567046810, 419486419, 1253143944, 66659843, 881230514, 668090206, 1511812945, 1016909170, 113220891, 1383679300, 25018660, 601042921, 617170470, 873847026, 2031785407, 268970938, 1757731439, 912299042, 888852972, 5768885, 1418396975, 1793099888, 1643983800, 222979092, 30486725, 1064322042, 1781613856, 1879528483, 664817425, 1631455253, 1580060586, 835661314, 2106930724, 1261481503, 636696092, 1076007434, 911480049, 928566610, 896808506, 871325053, 1308068086, 1303434357, 616934102, 33829218, 917554777, 1804014012, 697752408, 338439410, 1906923326, 1536860934, 1503331574, 508500145, 1508283478, 2000372644, 1828742743, 1654635758, 507532484, 1011473755, 37046771, 263003590, 1953534753, 915009605, 2114319696, 1396936618, 602311771, 618428739, 663098336, 888278364, 271360703, 19730478, 1705615927, 389386693, 398542040, 766898965, 677056803, 172191416, 1244387544, 2070784863, 616942027, 963997310, 773026832, 1345569254, 1201702211, 858829717, 62714432, 854748390, 22998634, 567518169, 1209096070, 1035691664, 493787406, 1970698613, 2007091187, 2113924690, 210566862, 419303855, 1273956801, 926096033, 2080906195, 1511767774, 864704485, 1907864361, 1951374748, 1424830064, 664817425, 2054771717, 1396804547, 455420627, 1138846091, 2015289373, 928484026, 1939076894, 1988764940, 1042331017, 1285768271, 167440201, 1379257910, 1511451248, 2090748541, 183723589, 74231091, 1257033275, 560059120, 1750460304, 345143437, 751161505, 84405079, 1173398932, 2133572510, 174807551, 815557018, 1816232138, 1318441992, 257907651, 519488348, 1004183235, 560772329, 1273161542, 767094964, 1255390812, 2025387179, 1049624702, 131345167, 2075981479, 70154193, 1332380297, 1385437618, 1387859176, 1492074493, 773073610, 246349712, 795800901, 1311388213, 230463696, 191917175, 2137570257, 1318177815, 1991002121, 270024481, 1240606806, 1245078435, 160070368, 1012813727, 359783845, 1786108570, 1805485695, 99473265, 753962400, 1323152131, 1699213782, 1991002121, 1573443332, 1299131130, 1367763955, 1886734761, 1990625570, 1778926339, 1846894959, 1411769457, 295491359, 1789053940, 540851265, 666865620, 108919360, 1951374748, 790151726, 2068377748, 1923964011, 1314248511, 1661915959, 1430064941, 315780798, 1824785680, 720410712, 1235575155, 899384205, 1603818820, 670159678, 1304211430, 81561422, 2058551894, 1741418282, 1556555846, 615558721, 223766969, 1338243986, 425279855, 1538799127, 2074273043, 643884630, 50009535, 367762715, 959487304, 621776839, 1742436766, 603313453, 1115872421, 1327050637, 856013819, 594615309, 762361641, 1417013841, 620623299, 307580735, 267831207, 1719831125, 318985923, 439778475, 652726475, 500681523, 1137681709, 904924639, 943232983, 1317087339, 1187751294, 1546116127, 1168096225, 1860627160, 164594135, 2027266245, 655887191, 443431060, 1510425997, 1012773338, 1387311701, 407154938, 1742045156, 1264939330, 498941396, 315631798, 608696881, 1744274428, 467923590, 978266798, 252999513, 674356474, 1246165376, 1222717536, 24859467, 1015903193, 
    //    1638832962, 2073741654, 1806545999, 2117980737, 804391823, 150860464, 568669708, 2732847, 1550482403, 1306445479, 914633060, 2085266832, 1422271500, 1197604648, 701948913, 438726876, 873847026, 1532102703, 1147769467, 518362376, 1228053553, 1593772889, 1884200899, 841618321, 120991963, 732638855, 1401177460, 1870448871, 1372260034, 642036475, 255131659, 879720775, 1270222870, 1141289255, 972580270, 545368663, 428396622, 239628966, 2001388563, 239807843, 870944318, 626395339, 740055996, 1426365633, 1005283921, 1700899364, 1478356981, 1814351551, 2111704471, 1435504072, 251272629, 1255390812, 74848147, 1929888017, 448198844, 294055099, 953084565, 169610119, 181031220, 180573962, 963997310, 439778475, 1708029154, 1532107625, 551597867, 88145971, 2144746235, 713672901, 576780426, 1213787068, 1376637413, 58654919, 1579703639, 577143729, 2027013194, 2071753573, 1348231040, 1563320665, 922426422, 11194533, 14742310, 1757701636, 1454898855, 1960553676, 1402571036, 1078547872, 1878277601, 42004903, 1936596865, 337213357, 2038245116, 1209096070, 1051199240, 1162358859, 1975474557, 380193002, 611997790, 2056381598, 2106029796, 721131672, 607053955, 1808693192, 1395100767, 967913121, 1634019272, 1545669143, 1094834472, 998279941, 1160418779, 1861905415, 58654919, 868065801, 35740529, 636912232, 719844251, 1721296419, 1264350721, 2071753573, 1303796069, 796862440, 1814351551, 1075649638, 695079799, 1387023589, 1254641799, 1932370017, 1852700557, 385376116, 1462230070, 590883438, 1458040154, 1799154706, 912740029, 560059120, 1921948005, 1159613901, 1133905695, 138942590, 2074717391, 1269343244, 2091897626, 816430404, 328804905, 2003272511, 1315420570, 102469647, 525367950, 975600516, 2090006544, 1799665758, 568146809, 123310019, 805499097, 997266633, 343229265, 1916913646, 899695015, 1708520997, 170568690, 1207131097, 1151508937, 1169547994, 1075229520, 2021995410, 363321932, 1838792369, 1322994336, 312683054, 1264939330, 658422407, 137119997, 2046342720, 1684381188, 128928726, 1308068086, 1127804894, 149736693, 1130657956, 493787406, 317328226, 1188528596, 1600373394, 525595959, 79161108, 813114273, 1834296774, 705807554, 1466503212, 202961462, 1349386537, 681775189, 1085765563, 1071422160, 236509131, 1746167885, 172191416, 1210681866, 93465029, 290389997, 2067470101, 1019066051, 601042921, 1138603746, 1169547994, 857396809, 418681184, 1318177815, 1646813814, 334567518, 1004094984, 1327589513, 1363924170, 78650663, 1644544197, 1014111406, 70573173, 777653239, 413466639, 389453622, 359494534, 561001559, 1952404090, 1920593, 872963203, 61925360, 784195479, 343819379, 2056163926, 519488348, 651673594, 698880388, 1735844665, 657337504, 1164660148, 582944702, 539966242, 257907651, 1273161542, 37046771, 188356918, 1608244402, 268559396, 111040003, 441802163, 522438402, 996623389, 740739813, 1944566459, 376564302, 279980936, 508064377, 589352278, 718194044, 1842157899, 279980936, 108482691, 1560956680, 2023692229, 616942027, 1343151144, 1857462107, 1060947640, 1012813727, 1327992199, 1437471375, 306215694, 573894609, 598312960, 1771943912, 175277739, 258122431, 919484816, 1494527097, 74231091, 30049307, 346103644, 1320712771, 1618878465, 1886819148, 1254919095, 1862294135, 240922878, 1310093897, 523488422, 258631274, 1357895568, 302904351, 1742436766, 1152274190, 854748390, 77183124, 2038245116, 411719865, 677955187, 1729550368, 644419809, 2084373316, 673450766, 188502069, 1652121057, 850439096, 1165050953, 1364507603, 514274459, 2058551894, 875389639, 1034668070, 677056803, 37139523, 1924219317, 401578409, 2130853680, 2086316860, 554305881, 552078463, 428396622, 686927609, 716470693, 1013265168, 1701794432, 1363182895, 1170220406, 807027288, 1291907803, 113773003, 49604905, 319317113, 980907223, 1519114125, 406201474, 754929893, 2137181293, 1909104176, 1499698026, 849601284, 1306134223, 1882458523, 595750919, 259034488, 1365211750, 453148571, 1344027472, 399606167, 722974384, 292735214, 237963787, 978628216, 1875749845, 14164829, 1183430566, 1177399994, 1494675360, 1524611285, 1055006562, 1376953390, 467289721, 812952582, 1147385247, 686702452, 1736295572, 1857557708, 619679807, 1303796069, 646021739, 1672978605, 736712894, 1537919837, 796033879, 1705615927, 2045644546, 1152011317, 14700543, 617558016, 1707471039, 858974514, 2138215875, 1485671329, 1483226305, 1396455995, 1209096070, 1161683416, 1218185218, 1905457709, 859910326, 1945203110, 1604627318, 1213787068, 398542040, 1997099363, 540036356, 1303448950, 1750190831, 881488639, 1124767833, 2002145065, 1088553864, 506409043, 1766840193, 724110221, 459200749, 188502069, 1805790989, 1794756251, 719844251, 1125323063, 759147960, 338439410, 1853528732, 189133073, 1157235330, 781251781, 85954495, 1165050953, 256773240, 639803614, 1349036922, 923674491, 430395950, 1076122222, 737991175, 528327465, 252999513, 623816090, 899480896, 868065801, 1455684643, 1862336190, 1790076318, 81561422, 1705349252, 2106930724, 1402531066, 1642137852, 59295167, 1964610457, 1075269657, 674356474, 539496541, 1531220755, 1239627543, 1376030440, 1201149043, 859549329, 717717048, 1846894959, 754929893, 872963203, 725527492, 1549166473, 994729639, 1964048383, 1718274188, 621776839, 1485349566, 854748390, 1367763955, 1152339406, 61949619, 1077715703, 243473124, 993356359, 328680096, 1208633975, 76329331, 1523987634, 681796983, 642533712, 1631393442, 749323567, 458981757, 1151338385, 160070368, 1207131097, 1822671887, 1387311701, 1028101034, 151102356, 580675343, 1409835681, 1356397992, 1262225938, 720101928, 294978747, 2048660941, 449175565, 1409324561, 1492074493, 1510606642, 1658573207, 249925290, 136506361, 188356918, 1604806597, 1735844665, 1207213487, 1183430566, 145058805, 967877199, 61787709, 1201275221, 461930724, 70154193, 1557848530, 1378967006, 726612073, 332528938, 73260907, 2024257868, 1939076894, 539491282, 1744930556, 1043384720, 1342784702, 785111139, 1271900685, 879720775, 1944177349, 2027013194, 716781081, 1412133344, 1171417911, 582365369, 1775479304, 74226018, 1853361948, 1496225925, 1850541963, 1868736986, 1771943912, 894867366, 2699240, 1238652484, 596370481, 863714478, 154822930, 1613889932, 1221566986, 1291907803, 732417423, 327922866, 694840627, 1644674512, 2024317609, 909059671, 2107289626, 547464822, 1305803021, 858974514, 1552755694, 1205980414, 2006878901, 563289155, 1651268183, 1355858926, 1804321259, 1349411090, 926697640, 1080265295, 206242713, 540680368, 2093456594, 1278710507, 615558721, 1601986079, 1323494158, 1959715134, 457189095, 1828742743, 387794786, 2059482807, 142564263, 1221213295, 294978747, 1720734723, 1895949995, 191917175, 968946055, 2147012933, 807362761, 328894035, 691147134, 1571122572, 497709030, 2093240823, 314591, 662103946, 1551803911, 843188383, 1188528596, 572175780, 1869961542, 1234076025, 1643656184, 641411139, 357446090, 1975060060, 1791805686, 1347441462, 1508578080, 1396804547, 1971040710, 276784564, 1238093883, 987895876, 267831207, 1208296014, 1072335882, 1706364724, 1556405980, 1125568125, 1689061365, 2067399680, 1846894959, 727290358, 1044817425, 1818255155, 822686065, 736414309, 1767853591, 1604806597, 143294963, 1519438783, 320072214, 603388061, 405256043, 2100800063, 616912329, 636681142, 2123156216, 143294963, 223005764, 788276282, 487124508, 919484816, 673450766, 542198534, 52831353, 1483662604, 527911378, 1071836509, 1772062880, 268559396, 1769258509, 70297915, 1875189672, 1491775538, 1851576207, 1048758132, 1362476595, 2123153915, 320041772, 1285768271, 11336464, 1465071702, 2030186208, 1314248511, 136105816, 1108936063, 74226018, 1537789034, 430395950, 76329331, 657978301, 1223438798, 1148226832, 1715065571, 34673913, 210566862, 1436931100, 526901852, 2086003977, 1276871085, 1878339486, 139675142, 333825440, 828343957, 1512893015, 251272629, 36906986, 1153396558, 501689583, 918433206, 493084626, 998857403, 1704669716, 242590710, 498342484, 114547009, 1138846091, 459200749, 159335461, 1181300623, 1945408679, 940171623, 1555941991, 1177399994, 162176695, 1561587874, 37139523, 1571852620, 2132253279, 1169499557, 636681142, 804500684, 498342484, 1223438798, 1080438979, 232647782, 508566931, 464498110, 753909491, 2034758704, 210582579, 1622955755, 1281036306, 995170030, 428247507, 253824192, 1903908334, 406201474, 766786608, 1593286454, 1137681709, 709260923, 2107289626, 1304872872, 136033084, 627508865, 2021995410, 956235134, 430552662, 1257274582, 1518494121, 62791287, 599327109, 672352493, 706324133, 1584702197, 838119681, 958071775, 1716637928, 257907651, 1264706694, 328242555, 453007386, 720410712, 875389639, 489314387, 1798892449, 2049474593, 1685783349, 1941774667, 231798475, 1976618412, 1264298557, 1355858926, 1754981562, 921819989, 272551264, 1278155451, 1083973675, 129433537, 1460365676, 1254641799, 1037616788, 1621676102, 1380894137, 30486725, 284891577, 1952404090, 782561739, 9102820, 1147491775, 599967314, 1306134223, 1826480243, 112619849, 899480896, 721131672, 1379758814, 1442296666, 582477025, 1311413985, 1485811481, 1201275221, 84092947, 253204657, 1620418221, 1445450721, 1338303831, 1346002994, 2143685121, 197927219, 1155492279, 2035113961, 11381248, 1939076894, 1826480243, 780479715, 1981297701, 640278640, 273379488, 1206296453, 1608781954, 1344027472, 1367763955, 1376050426, 1468805928, 1956099809, 89012233, 1046486641, 280282651, 2112668892, 1938242861, 711842369, 1217080259, 1732556898, 629945856, 1538799127, 923679922, 1011217885, 2080639578, 452860596, 495013822, 1049578106, 704196901, 151109077, 823065319, 71465821, 1884318008, 1770405445, 379005158, 518814904, 967913121, 888278364, 1689415715, 674768671, 1938242861, 1516821127, 542986325, 1417286567, 582676700, 1938001746, 516449724, 169852557, 1281036306, 991699344, 1231005351, 663098336, 2069771726, 1797937840, 2043668064, 1197611032, 2027688546, 2127436999, 1705615927, 121284735, 1894380707, 292974750, 1410954411, 1108373797, 1403649304, 232765397, 1744930556, 1479529708, 141937112, 470048799, 179945569, 1283126345, 290815972, 123104157, 1100855205, 670159678, 388525603, 244683660, 452131788, 1436018378, 1412919770, 1750226398, 18631163, 1181231251, 513084761, 895948646, 694487695, 52583288, 446159266, 1800770880, 2074273043, 2137181293, 1195416317, 982098496, 594615309, 595383327, 2146379908, 1560956680, 607053955, 1543490814, 959287618, 301216582, 622048148, 894874961, 1332380297, 728091867, 725527492, 1375081504, 750826293, 1724354527, 258631274, 726913652, 1689412633, 1427628789, 1168096225, 1766266922, 1553144697, 9396212, 1194314226, 1346002994, 199182824, 745862339, 2130785565, 1223111467, 279980936, 865844387, 1775479304, 175598738, 801618595, 1310093897, 912365222, 677497477, 858267769, 1541030844, 639517117, 139599021, 932764615, 1725552225, 1349386537, 639517117, 1026794261, 2067399680, 1169499557, 948980666, 2074717391, 1064428753, 1665245194, 1546820945, 1291493027, 50123905, 618572572, 166050056, 1850267754, 407735949, 339055560, 1417286567, 630652619, 1921948005, 1952672227, 253204657, 1378967006, 418542232, 1436018745, 1127127979, 600821543, 291807980, 2007091187, 811480634, 689107975, 1008225498, 594615309, 1382497496, 324271879, 48409551, 2134351533, 1633777983, 1844851837, 890547165, 1559213812, 724133082, 1656403750, 1046005902, 1815263816, 84757944, 768710633, 1885850928, 582365369, 920286748, 134168194, 2117543578, 2129184081, 291807980, 30455058, 1491775538, 1222867743, 210566862, 730274240, 1622631246, 665770747, 1222144333, 542986325, 247274314, 1034032416, 1325056774, 523459333, 331555829, 77183124, 1439595887, 82073308, 1424830064, 1048317101, 810988877, 1706364724, 1890830822, 2117543578, 973922757, 718194044, 1147593589, 281043528, 1791805686, 2141313080, 1066665267, 1396907779, 837896186, 617719969, 914629741, 686196847, 896808506, 1812691524, 416012800, 563563642, 2145244822, 14700543, 1486305037, 1694085834, 1083265348, 607053955, 2071753573, 801618595, 14742310, 917686375, 1613281447, 593450337, 677661848, 1450623777, 199022292, 1103316090, 177867297, 387156772, 914569165, 1719831125, 677497477, 128928726, 821907359, 1579661247, 1342784702, 880522474, 248312911, 1026048961, 290319176, 171966258, 865844387, 199182824, 497156672, 945846833, 1349036922, 1647251866, 1970275095, 471578550, 240922878, 826110622, 1396884988, 296620453, 1363118083, 1524611285, 1057603270, 1788735617, 1703120002, 532543921, 730706747, 1096020823, 633327842, 585376768, 2089306052, 1177399994, 1766900287, 1441139101, 913409696, 1344439218, 320962708, 1511451248, 147531315, 1530809038, 106677026, 1653561548, 710371222, 1734287064, 267597008, 1877966605, 958124398, 704841048, 822577542, 859413832, 1426365633, 145985700, 46552310, 735836075, 724110221, 760002861, 743808137, 2134386512, 1413045513, 789340727, 2081705546, 1556555846, 168610581, 1711387613, 111433058, 639072080, 2118039687, 704196901, 532061936, 1265741480, 1512217632, 695079799, 1754981562, 603313453, 1985615226, 1584713478, 387156772, 101982632, 1310093897, 1064322042, 64367067, 1886734761, 797665756, 236509131, 334598901, 1761753757, 608920218, 1547390000, 1555682882, 1960621549, 1376050426, 1046486641, 1325194608, 1944671873, 429348027, 1939698, 1321471874, 1810703039, 753947465, 1347054102, 1442585080, 2069771726, 1621676102, 325439108, 1766900287, 1688471765, 855768173, 582481940, 489314387, 1096020823, 373800981, 341083512, 376564302, 66525416, 310702305, 1512893015, 1449961287, 827360684, 1518494121, 1164440511, 865844387, 1782116234, 1477785817, 1093691062, 255131659, 2082060481, 63965140, 1638450216, 813114273, 1133509292, 1183405041, 1618878465, 1597162990, 1665066176, 536235410, 29109407, 290319176, 1952827627, 1832669442, 1557848530, 258452072, 1075273376, 1429190438, 1436931100, 946909849, 21442201, 1131099352, 860200500, 1252058211, 1162356721, 141968436, 202961462, 124247141, 849601284, 93158142, 1463708231, 273086001, 306215694, 159245676, 442048367, 1110076823, 1581367123, 1505389493, 831283442, 397642685, 1468739619, 600825961, 1691729820, 1561485504, 880201954, 1890830822, 419793410, 1129964453, 1063970512, 487124508, 480110638, 1680560874, 801064725, 621076266, 711842369, 162969804, 540851265, 1452755824, 613683320, 2100334854, 444549833, 2048604124, 357446090, 1026794261, 1195046996, 1222144333, 1271438811, 2130785565, 201055019, 1665467551, 51942689, 277315685, 136105816, 1699213782, 18859033, 1456846153, 108027163, 268559396, 1834365418, 726612073, 1197604648, 835661314, 1013265168, 1275567711, 92630830, 2027896173, 446159266, 1050205021, 50123905, 1941774667, 2123916736, 850439096, 175277739, 209746556, 35694755, 1296133422, 1383679300, 1048135095, 1828888563, 1944177349, 1152274190, 223005764, 780479715, 1285860224, 1262225938, 124247141, 1816188605, 1435707183, 1599008760, 502690372, 1008414920, 704841048, 420878795, 1941758098, 242609728, 362543248, 2088438151, 1462720740, 1857462107, 1446700399, 1137722280, 458272493, 1162775366, 279138325, 290389997, 331479057, 2090748541, 2055232873, 1265510028, 51207448, 718296482, 10686441, 1884318008, 1482279908, 968397899, 804391823, 1124945499, 836520453, 540036356, 494069859, 1661239006, 223766969, 918433206, 888852972, 1715065571, 634539753, 365089823, 128928726, 880201954, 1095183875, 435888132, 2142066949, 1722450996, 1374659657, 345368590, 43739628, 975010270, 52583288, 1340703404, 1865170382, 1852700557, 1865368027, 1706679679, 841509146, 9168396, 1203461153, 1176968507, 1602437445, 1157867780, 1969222382, 909436300, 908807247, 716781081, 554305881, 1033885955, 735100554, 1013265168, 1973092982, 269751562, 1760598030, 2019659293, 1496155996, 183771382, 1409020242, 1537926203, 101982632, 517530367, 464235269, 1703120002, 1856377284, 886911849, 230382393, 822577542, 1817518320, 587320041, 240606866, 605724786, 23114128, 732572932, 963461718, 796357935, 102991889, 276557765, 898546706, 1957653175, 2056163926, 78650663, 682243247, 113141376, 1569187021, 428247507, 1309029058, 935638289, 732417423, 1018192457, 2016607359, 484859646, 1095687519, 2131799330, 292390521, 750241107, 1046005902, 1834316462, 1333945399, 1249030677, 970479397, 298037935, 807362761, 420878795, 1812691524, 102469647, 1882458523, 214619324, 1195046996, 807362761, 1522160281, 22998634, 399591481, 231848344, 333825440, 2142066949, 2077535535, 339395771, 1816232138, 234000828, 50009535, 671522903, 320904274, 386054492, 1810205907, 1538799127, 1010428964, 1800875007, 2058624704, 767094964, 2037000131, 1069246343, 1868736986, 2029787528, 1964468412, 1865504928, 871325053, 1817518320, 1549166473, 593199673, 1170220406, 1411856781, 574669571, 114547009, 1450968061, 305646046, 878106967, 822577542, 1909104176, 754005324, 1781617161, 1624414188, 411538627, 1828157509, 861989552, 1771885870, 378274606, 1705349252, 279200661, 537077189, 862213962, 126515687, 909436300, 1909262549, 188050376, 1072185424, 277315685, 1384723041, 303661871, 766898965, 1409324561, 768710633, 343819379, 788276282, 514902004, 527762521, 936087306, 1431405251, 1725552225, 1376030440, 484859646, 362543248, 138942590, 232765397, 1973092982, 1914610538, 2090897212, 1688471765, 712672222, 551597867, 2025387179, 1701794432, 1879528483, 691079513, 1165788209, 1433067572, 53206536, 7421568, 1810703039, 2055232873, 1413707760, 1885968303, 1816138556, 1631393442, 1048317101, 18307937, 1031165880, 108482691, 1304211430, 448600121, 1420926612, 206395892, 995490919, 1355846053, 223121215, 736970774, 1433788673, 276784564, 675772546, 1917488415, 850405168, 1449275702, 1412919770, 1333525609, 1733253101, 1857780184, 762361641, 126515687, 32789456, 1908041391, 1111794337, 1545709767, 624545635, 1473175110, 685470560, 1918193498, 426573051, 749323567, 1062998149, 1503331574, 1262365446, 1322994336, 331479057, 989287744, 264562101, 1633199358, 1151508937, 1187751294, 183723589, 20954011, 752256265, 1203503499, 1769258509, 874059158, 270823204, 1325342998, 1966868632, 2088353326, 2084863511, 444549833, 1010928145, 1945051621, 596370481, 815557018, 1259369261, 1651666404, 639072080, 272512753, 858829717, 1281237028, 426649736, 1120224391, 1783466941, 1833291826, 285043878, 809793505, 2101917261, 1799665758, 1032452336, 811260198, 775512745, 214736090, 136033084, 1409154107, 724110221, 184792528, 858946596, 837896186, 1411102047, 1300391206, 1381265949, 516449724, 1960554950, 1198330111, 1885968303, 1270842164, 1795222379, 859549329, 1954893475, 2087786971, 1124945499, 1581367123, 600821543, 253204657, 1768039834, 457923849, 1520307502, 290389997, 772347915, 999904254, 398056255, 1834140620, 523488422, 1596807024, 1633199358, 1264350721, 1224399896, 1184638371, 1057603270, 331047763, 1069199928, 94588189, 48808513, 11194533, 179945569, 1749947805, 724360342, 1139098337, 739483285, 641411139, 1048135095, 1980106071, 1934336201, 502112347, 1355846053, 1656403750, 1650535552, 264562101, 2078928603, 1118590297, 532299899, 1290018671, 360021262, 606807065, 968250182, 1413045513, 831283442, 273379488, 975010270, 2027013194, 1090526942, 1038981691, 1016909170, 754698179, 1494527097, 1793341706, 851626142, 1954714276, 1124452456, 25493886, 1379758814, 895118842, 1761896418, 1884318008, 1151508937, 38606351, 455420627, 2100248276, 1251033895, 363321932, 1227426537, 1666459717, 694256689, 979361639, 169417523, 1555941991, 1317995768, 68494243, 388525603, 1345569254, 1804321259, 409281076, 1393983330, 1774732562, 991200353, 1677309560, 2082097207, 736068476, 1930114840, 908881511, 1141992919, 1007437634, 1760527776, 1674290667, 2132253279, 2017618050, 818891051, 517530367, 1080067, 816811738, 1587354907, 706298499, 610722474, 343730055, 906238786, 1329109980, 1386008831, 567640797, 1534316369, 1291286760, 143506880, 1539356332, 1004697089, 1247822739, 2039905320, 1959440039, 1684852678, 23114128, 214825164, 1550438867, 43739628, 2009394068, 73260907, 1284372870, 586645833, 1051699659, 1329109980, 1704669716, 730706747, 1725275294, 1843066414, 1018757103, 1700857774, 1331444372, 1972392443, 769627492, 731365818, 80129317, 1611706597, 904362970, 1356844070, 1753989954, 1144093133, 1137211517, 2090006544, 1912940964, 1559213812, 493787406, 898546706, 9396212, 673635802, 549074999, 764421303, 2028660000, 307298640, 17911512, 1117033075, 670159678, 1975474557, 151109077, 1018192457, 513084761, 1396626111, 989287744, 222457627, 953084565, 1534639450, 290573083, 324979793, 129649389, 1161683416, 1234591307, 500134357, 1667625882, 2072190634, 85587158, 1452159314, 463494602, 576533870, 129433537, 1821959069, 299675870, 2090748541, 795788279, 21182638, 2127581327, 415985338, 1363924170, 1510425997, 1597468066, 304668660, 271360703, 84092947, 43558549, 526901852, 339055560, 1923540173, 1314248511, 1271900685, 1676627757, 1190952023, 547513197, 1611060339, 1333945399, 297949086, 307073627, 1742624200, 292735214, 2055160246, 1269617585, 1850541963, 194264310, 1075229520, 2016607359, 249062960, 2059482807, 576780426, 170432640, 48808513, 290994914, 239807843, 557831566, 1727873231, 1675938272, 1573657704, 2095052868, 194765507, 1890855407, 1284372870, 1194003972, 1094834472, 1527662877, 526901852, 389453622, 721704302, 2045644546, 173182251, 1108936063, 1956099809, 1343828193, 547938803, 1539356332, 652726475, 209746556, 2027266245, 1915026764, 2023856660, 14164829, 1755481145, 1340977251, 2083002453, 1271417447, 1360545690, 672352493, 1766840193, 1443483909, 821114813, 501689583, 1025803124, 1409324561, 1680560874, 1463183151, 1555941991, 455420627, 320962708, 1296133422, 61787709, 1254377714, 1153396558, 337208013, 1853528732, 206242713, 143506880, 1438032980, 440158160, 1349411090, 458272493, 1197611032, 1460365676, 1157008126, 1588915892, 1439595887, 1012773338, 428978032, 1881920118, 2119617991, 185042550, 951380020, 447793890, 197927219, 855768173, 113141376, 724748364, 861780118, 1573443332, 713781700, 1802201929, 272551264, 88803521, 1323494158, 611997790, 1362302859, 50123905, 270743376, 641419685, 1043514166, 380749810, 1323494158, 495013822, 753909491, 1193228175, 494069859, 1074901043, 2043668064, 2075534857, 202564793, 418542232, 1789053940, 1493851605, 1252069834, 1914268056, 547938803, 1393983330, 79161108, 1334034467, 298037935, 1913013578, 892582892, 367714288, 301216582, 256233144, 92630830, 1589400660, 1207213487, 1964610457, 482273390, 256070957, 640232726, 1187536839, 2073966494, 440098639, 1347054102, 474993201, 885127795, 1205529761, 996409360, 1680560874, 1188209276, 2006878901, 335919854, 432803527, 1263170135, 2019659293, 1144128347, 1078768214, 2133572510, 2137620566, 1552176400, 90549767, 1675313998, 1426365633, 1062998149, 2047425499, 108027163, 1988411269, 1326546568, 168610581, 1438349914, 26100274, 2058624704, 1171414364, 2048701843, 89578559, 1707471039, 908878348, 1211226518, 1509187955, 1933152779, 1786108570, 1217080259, 1263723060, 1821959069, 1175573678, 1878882487, 514274459, 1437471375, 1034503334, 1666286463, 1913013578, 286777909, 1137722280, 1463567802, 1034032416, 2084863511, 384952692, 2024317609, 1245078435, 1004183235, 1169851094, 797216509, 1498850799, 262134483, 1510038904, 327922866, 418681184, 1055006562, 1859739146, 525367950, 1368196138, 30455058, 179841665, 908878348, 858946596, 1509187955, 77482413, 2025874135, 2055511346, 606336526, 31095436, 1553144697, 1292021335, 521517401, 1158011920, 405256354, 832822696, 801358, 1471137299, 276784564, 139675142, 823163860, 1981297701, 763350414, 2030904675, 1507259953, 1064428753, 1509300510, 1378500814, 2128082016, 416012800, 187309166, 1283126345, 1211226518, 736042752, 272512753, 660279180, 2047425499, 866269319, 482369170, 93909406, 1227426537, 1816138556, 1757902382, 2035113961, 242609728, 645037709, 1988411269, 1013551687, 117428582, 1371309940, 1643983800, 1293398167, 149016291, 1348231040, 1245078435, 290994914, 1252069834, 1561485504, 778533345, 1282233723, 86564517, 335919854, 222457627, 829844668, 1354565088, 1729937875, 1584121424, 1284572831, 1912533912, 1851331227, 191693591, 1834296774, 160630711, 1914268056, 22998634, 2024620261, 1325477525, 1427499379, 1641303651, 1996993015, 1728175502, 484845269, 1886654115, 466230576, 732360464, 223559202, 1855698525, 700429215, 1626068947, 956607105, 892582892, 509174426, 256251800, 1540343346, 1442585080, 1977288849, 2085170937, 2054771717, 42004903, 387459051, 1222717536, 2144704787, 1452755824, 975175262, 978266798, 447793890, 1805797459, 2047566941, 149016291, 1333827656, 1098192223, 1959440039, 1443349587, 608080381, 1783466941, 1745188664, 900688240, 991749800, 1311915472, 310378483, 721212094, 1225009754, 823065319, 747680098, 697752408, 378742434, 1147042578, 1814364317, 97342142, 706298499, 1264639055, 1745188664, 1082688671, 751669215, 1891724238, 1396626111, 1906071809, 1015903193, 472797321, 842384086, 2137089434, 1162356721, 1885850928, 1638450216, 1608111014, 889792282, 1102842106, 183771382, 1530663608, 976541484, 1271184549, 1340045982, 1446700399, 1181300623, 1600628410, 1631455253, 1483813177, 797665756, 387156772, 1355330826, 175598738, 1157235330, 1206680576, 234192250, 1682279037, 1398779834, 899326350, 797632039, 2009466687, 1991147180, 258201563, 1243203015, 1211361461, 1642853097, 2123156216, 297540100, 951195037, 1051857506, 304668660, 1975949253, 489314387, 935638289, 2123677207, 285276315, 634031302, 1231005351, 2010126824, 697552309, 568146809, 1308077549, 279376844, 894867366, 1252058211, 1167970994, 1562348552, 1430064941, 577143729, 1881920118, 676084940, 141972027, 1141984247, 1393691518, 13802668, 2016651138, 1997099363, 234033724, 289683341, 1735915671, 1862294135, 118420760, 1235720890, 1486997778, 1537789034, 46552310, 1156128924, 1826136669, 821907359, 2143343429, 2144903330, 782561739, 35740529, 547464822, 1030589043, 2085170937, 458981757, 775942328, 1708029154, 1422563275, 635003451, 76405757, 388946128, 48165603, 1487418944, 600821543, 343444919, 752817040, 435888132, 43558549, 827875919, 1675066569, 773899600, 2050618997, 1222988020, 1428518304, 1470048459, 397642685, 1566714917, 1063970512, 1493851605, 595383327, 203560754, 1509300510, 1049624702, 1046209055, 937135406, 509715204, 1159613901, 1395100767, 1270842164, 1939698, 936820699, 741462593, 1699213782, 1261388047, 899326350, 243473124, 1909262549, 803146391, 1430637984, 1511767774, 1843066414, 968397899, 188050376, 862973450, 384171436, 1004094984, 524697654, 1370686942, 1499698026, 773026832, 2127509839, 1005283921, 1534639450, 1095183875, 525595959, 1712007017, 199182824, 1125323063, 939097123, 351796145, 1672978605, 508566931, 1360545690, 1659934711, 1885968303, 1765871333, 632678922, 1094834472, 1009601766, 1912533912, 1244188176, 1064428753, 419486419, 1895949995, 1875749845, 367762715, 285043878, 776013422, 1668501665, 149736693, 2134524630, 1364342951, 36206165, 1719831125, 801618595, 1137211517, 1251033895, 1728087461, 1133905695, 258201563, 1750190831, 297859951, 1496225925, 438726876, 1537370981, 1401665198, 447104596, 608696881, 640898418, 687723897, 1887076741, 797216509, 1075649638, 1511679135, 2128135494, 1288190602, 166636431, 431401920, 2113359811, 1643061339, 2083669856, 1442296666, 884820756, 1137722280, 1004697089, 669024534, 633193961, 1742436766, 2038039768, 2030904675, 11194533, 93909406, 1537370981, 96420916, 1325194608, 1078541512, 943232983, 1406915594, 1609459107, 77482413, 1589400660, 1712663332, 875380348, 1195416317, 426573051, 1661915959, 1442296666, 1681487778, 1675226280, 61787709, 289683341, 917686375, 673635802, 164594135, 634031302, 1665467551, 1121864383, 380193002, 359709640, 1915026764, 158403416, 677504106, 2010126824, 1732556898, 368910908, 738467374, 1808419406, 428396622, 424696730, 835560621, 736970774, 1338087899, 111040003, 1862336190, 1549965476, 287193693, 1291493027, 1730690043, 963911031, 1842157899, 523245686, 1649751675, 1802932458, 612765355, 939520654, 345368590, 621076266, 323243085, 1561307592, 1713712401, 684722053, 839897378, 2047566941, 1997395716, 1997395716, 1357391752, 401578409, 769627492, 1865504928, 1667625882, 387231094, 1483328308, 9168396, 794089417, 1459288635, 1051199240, 409789802, 320904274, 33829218, 17498921, 141968436, 1228849520, 2079290811, 89354251, 752987405, 1788735617, 1151338385, 1348946657, 1672176514, 1395100767, 421164797, 2020646568, 2066837724, 424696730, 2117831808, 1620861656, 1238093883, 1904415891, 141968436, 704196901, 1810205907, 240545952, 296995426, 1636291553, 258631274, 796862440, 1363118083, 735401071, 442636741, 1519438783, 715251833, 720101928, 861780118, 3365714, 373072722, 1643061339, 1465834955, 502690372, 1756558241, 2120954882, 736068476, 747559042, 1813679115, 363079436, 2080906195, 2003207683, 577466013, 538369511, 1046005902, 963221857, 66659843, 835682322, 158318873, 7795593, 1810205907, 461930724, 337208013, 1514427983, 93465029, 19676782, 1133905695, 1976524983, 169417523, 1250672890, 633282367, 1546820945, 1404230738, 407735949, 995490919, 1685783349, 122130473, 940171623, 1718274188, 1554754851, 610180905, 351796145, 1741418282, 147913269, 591110565, 2054638474, 1183430566, 796357935, 1964048383, 1534639450, 1933542284, 1914067899, 1047353326, 935047258, 1677309560, 2103005346, 1917488415, 89354251, 1166071620, 1205245327, 378274606, 1831510420, 1622013249, 915009605, 1066665267, 467854460, 1478356981, 1515893503, 133687821, 1470501006, 2002145065, 1443349587, 2144746235, 829939889, 1197604648, 994729639, 1442878578, 98066404, 1717690867, 1325342998, 951195037, 616934102, 835320212, 1349888499, 1273764339, 826110622, 1621936784, 660279180, 1555530818, 1890213014, 679758734, 428978032, 931678638, 818960863, 676084940, 1409835681, 57555755, 1521285637, 1729550368, 874059158, 1480107778, 795788279, 1104356906, 1418396975, 387320530, 2125733307, 1924219317, 63965140, 1218185218, 1666286463, 2117831808, 384508174, 1016796780, 2090897212, 767094964, 214825164, 967877199, 1498850799, 1952141087, 1834791475, 1611197180, 528124516, 446155447, 398977496, 641375036, 222979092, 71911935, 1810894143, 881488639, 415985338, 2123153915, 1206296453, 418681184, 1355598578, 353820494, 1944177349, 829412931, 1026928318, 1844853413, 1708194430, 572175780, 1007068619, 2080639578, 1554624323, 315631798, 32789456, 223559202, 1641469872, 1282233723, 1194172034, 554412069, 1947081405, 803146391, 575028848, 2039905320, 2012770895, 2114319696, 1924333760, 1169547994, 102469647, 1914067899, 1852700557, 1641303651, 261448822, 1540343346, 286777909, 1357391752, 19730478, 1699441673, 1403649304, 1571122572, 1741218797, 292974750, 1790076318, 328804905, 1633777983, 1135568167, 365089823, 1798982230, 1941758098, 1124767833, 767893538, 1672425171, 366897022, 1844849342, 1808693192, 1271417447, 223559202, 1539223058, 1594316734, 2082543486, 925309338, 548280267, 80129317, 1033885955, 727744736, 1465071702, 201848154, 1826136669, 1929888017, 1359245518, 1975704947, 1439595887, 2107289626, 719696436, 46644677, 1173398932, 2097727245, 343444919, 854747143, 1271438811, 1500032466, 108027163, 2070432557, 1422271500, 1665297998, 676084940, 1034517151, 134272693, 1987467060, 141972027, 1515893503, 1673811039, 1703105867, 1360545690, 797665756, 1510425997, 629523564, 841509146, 1387859176, 1412221520, 956235134, 1271417447, 1712663332, 86564517, 1731396689, 312683054, 1798982230, 1594990750, 763369512, 1512217632, 996623389, 2072190634, 1289387356, 1527662877, 1141984247, 409281076, 989668780, 1666628509, 1539938826, 1366951141, 1547556451, 1396455995, 1522730136, 91359694, 2055065655, 159428104, 699408806, 1869961542, 234185967, 1130657956, 149924982, 709260923, 1470501006, 530959399, 77915597, 114312446, 1608859846, 1683782359, 623828341, 67116716, 281196812, 2002847941, 532543921, 677661848, 668265354, 20954011, 1985615226, 1733253101, 1361437771, 1212355580, 1666901545, 1975949253, 421164797, 1660360631, 2084863511, 894874961, 498941396, 1131099352, 1835543376, 304994218, 1508578080, 736042752, 1723117227, 373072722, 987470597, 787424409, 1435707183, 1326691107, 1936596865, 2074273043, 953084565, 1723295543, 1947596891, 1884200899, 1766266922, 1224399896, 405789612, 1076913648, 1947596891, 1001064628, 719506395, 1102842106, 412794617, 94705270, 1711387613, 267597008, 834909679, 263003590, 1518213560, 210101623, 1094065633, 671543353, 987895876, 1857780184, 270743376, 908878348, 1520307502, 1068212119, 1595297232, 1427722127, 1216971660, 1785904403, 1608244402, 20893955, 1964091132, 1332785199, 302904351, 1524665614, 508566931, 2081373870, 474993201, 1840179201, 720410712, 173182251, 915635683, 2033711141, 848587950, 629613342, 1004697089, 601309706, 1428518304, 975175262, 448198844, 962082753, 445946453, 369774785, 1419024779, 1382414791, 499681507, 1227426537, 1264706694, 1338962743, 1434633095, 2000372644, 1946678648, 1147042578, 1100200996, 112086657, 288339753, 783573236, 1757902382, 1143676418, 337213357, 335001283, 1371309940, 1323664802, 2074085640, 1380894137, 2088381338, 413466639, 1007928477, 494188454, 1051199240, 1945051621, 1010428964, 323147739, 1470048459, 987895876, 296995426, 483636114, 1032452336, 552168977, 201890473, 1074793835, 409789802, 1465834955, 747680098, 1255390812, 1342281711, 324271879, 1387311701, 1355846053, 1508283478, 468820279, 719530340, 2116951779, 1338962743, 887405876, 761314755, 1395884151, 2055461820, 412569264, 519275504, 1637634637, 929010963, 1121864383, 751669215, 346103644, 573894609, 2024317609, 1832669442, 989634102, 35522099, 1665066176, 128828335, 991651284, 1193228175, 1671433217, 1316357157, 290319176, 169852557, 1676356044, 963221857, 1718226263, 2142066949, 508869353, 764421303, 1674200383, 1564000796, 1347054102, 401578409, 1908041391, 843188383, 1779829776, 2167163, 264562101, 1452096090, 484845269, 1283651019, 766249601, 83075013, 1924219317, 962654654, 307580735, 737991175, 432376965, 1851331227, 996409360, 432376965, 245268044, 9168396, 1175573678, 616203666, 726612073, 1853528732, 1442878578, 633193961, 159396869, 70297915, 884820756, 1031165880, 1816232138, 1641303651, 288339753, 1730690043, 1402571036, 1735185224, 1010010937, 2134351533, 775942328, 1229158282, 1162775366, 126515687, 639072080, 598655629, 1921948005, 1251373739, 1999828290, 679758734, 1411856781, 630652619, 1262365446, 560772329, 1511812945, 1810894143, 1431405251, 1454898855, 1204432553, 442636741, 925959346, 893886641, 1601986079, 1175464638, 398542040, 1806545999, 1327589513, 197927219, 2054638474, 316195952, 1691759934, 159245676, 1291211056, 933753982, 1563829362, 1139648749, 1806274867, 1074793835, 1311915472, 816811738, 2115076912, 826120529, 1449961287, 575641267, 636912232, 141900477, 399591481, 942006131, 1060947640, 598655629, 1157235330, 1073079793, 586645833, 304994218, 1598733964, 1806822250, 1822527197, 271782845, 1816138556, 79161108, 1443702350, 2035113961, 1323993541, 162176695, 2097604982, 1257274582, 1401655241, 2103005346, 948980666, 1248109576, 295491359, 797632039, 2070432557, 976302754, 1103316090, 1080067, 1088677400, 633282367, 102991889, 1658797403, 60023007, 320072214, 1552176400, 1618021623, 1875189672, 1566714917, 532150406, 898546706, 446867388, 1597162990, 1713471852, 1470501006, 166050056, 417586065, 164551340, 1300128894, 106677026, 1166071620, 427349270, 2140408751, 1183405041, 291984552, 1741418282, 1208296014, 1905669453, 1119892765, 547938803, 412794617, 2128082016, 1324752892, 190352713, 1384091771, 1663611101, 555039840, 1997395716, 1343828193, 1779586877, 573123388, 516597192, 1222717536, 1153082341, 307298640, 372226306, 961523717, 199382152, 1240878843, 652726475, 1263723060, 1511451248, 764421303, 751669215, 266357059, 1666901545, 1181231251, 976379823, 367762715, 1775479304, 1300128894, 362918215, 1561307592, 328242555, 2117980737, 1376953390, 1770405445, 1886654115, 118026439, 1865368027, 1223438798, 188419003, 1793341706, 1584713478, 1056851669, 626395339, 1462720740, 2145493341, 468077147, 888602298, 380349092, 945413520, 2147012933, 628084195, 49604905, 942165348, 1850169472, 378742434, 727549138, 1462230070, 1344439218, 590629426, 611997790, 142444800, 538369511, 2070784863, 1929354053, 1802932458, 2106366714, 1269343244, 1409835681, 639803614, 1321471874, 858267769, 777653239, 843188383, 506184654, 699408806, 771215411, 1642853097, 158251385, 617558016, 63037272, 551276231, 1668501665, 1383679300, 1475074700, 1343151144, 664796600, 258613640, 62791287, 1795634167, 1866277049, 1419024779, 2017387197, 1676356044, 1271438811, 1755643328, 2038039768, 1760598030, 1111794337, 1292021335, 1522160281, 2134351533, 679758734, 1154674584, 405256354, 732638855, 801723862, 1684381188, 560583198, 719696436, 1744274428, 1047353326, 1773372283, 1608781954, 620932879, 1532102703, 1419545489, 727744736, 622671468, 880309423, 1462720740, 320539453, 201445383, 2101917261, 963597689, 612765355, 498342484, 2085266832, 60023007, 854672462, 1656403750, 239650766, 1554754851, 145985700, 869024197, 97342142, 771024103, 1865372880, 1760598030, 815557018, 153378523, 901240548, 256927400, 2110637321, 766786608, 1224228173, 784195479, 1078547872, 123262014, 2143449526, 1338436466, 740055996, 150490834, 239650766, 18859033, 1538150191, 1462513507, 1412133344, 761314755, 991200353, 1512893015, 2124071937, 2048896011, 998142625, 1741218797, 693807790, 614013617, 14700543, 2088438151, 1254377714, 1621936784, 1010234722, 1198330111, 2143343429, 328894035, 1263170135, 167440201, 241561914, 1675669717, 638089950, 316195952, 234000828, 1387461161, 142109411, 1076007434, 398056255, 834909679, 1281237028, 1213787068, 1193434274, 201055019, 1452100523, 593450337, 320904274, 2040984959, 2081705546, 1147588902, 1750874168, 963461718, 849139883, 1382414791, 90120712, 2112990879, 1304872872, 923674491, 619679807, 479609697, 642533712, 305646046, 1689415715, 1427499379, 150860464, 2030186208, 1069199928, 900688240, 1993316245, 231848344, 1569611228, 805499097, 653535138, 1477785817, 869024197, 915009605, 1014111406, 1831510420, 187309166, 1025767564, 948886854, 1577120247, 862213962, 1198593322, 560587689, 490333082, 593372864, 1381275627, 1324345778, 98066404, 602311771, 1291286760, 1198330111, 1694097056, 29109407, 1735915671, 2037000131, 483486458, 1552176400, 43558549, 1773372283, 888674112, 333712532, 1660502484, 319668703, 778533345, 1973092982, 1530663608, 828343957, 114312446, 1894380707, 379005158, 186991157, 1125323063, 464498110, 285024128, 718899752, 399955743, 361856386, 316656456, 1954893475, 1801313449, 2019659293, 1483813177, 842721223, 1976524983, 1430637984, 697552309, 290573083, 1126587027, 1205980414, 1454839130, 662103946, 883908018, 1348946657, 1236862663, 1868736986, 629343315, 873847026, 1671147232, 1594990750, 413466639, 2130853680, 1717918563, 1253143944, 1308077549, 1653561548, 899384205, 1314381526, 1269783183, 139675142, 401113842, 271782845, 234839644, 1278445438, 1493851605, 641525347, 1085542797, 1212355580, 1686843282, 164551340, 1130972654, 137119997, 1977288849, 256070957, 2048896011, 1714179101, 333712532, 502690372, 1922585086, 477843186, 1431652882, 1083973675, 707579938, 1064833324, 2127583276, 1120224391, 2699240, 2086900020, 2095133043, 29109407, 681290040, 447197919, 145919859, 160630711, 1808419406, 416286878, 70713037, 1712007017, 1305803021, 500470549, 908807247, 986703790, 1261388047, 808201781, 1261433119, 1818087300, 2100800063, 624545635, 240289951, 384508174, 2077535535, 1078547872, 359494534, 1409154107, 514902004, 1561485504, 1043354926, 188050376, 915974138, 1593627485, 317328226, 1390687643, 1367500359, 162969804, 1666901545, 2077535535, 1246165376, 574212187, 1254919095, 501689583, 1917488415, 1676627757, 1269783183, 74848147, 1839290080, 1087715502, 1598733964, 1364281340, 583355361, 151102356, 706324133, 1939584521, 735100554, 80852967, 341083512, 516597192, 619679807, 1931582241, 1381265949, 1632349255, 1628918914, 98066404, 1354565088, 1249030677, 174807551, 1810703039, 1600628410, 1039595273, 1118450555, 754698179, 77915597, 1130657956, 1877966605, 1638832962, 338439410, 470048799, 1480107778, 1175630307, 1779829776, 668090206, 1222988020, 1224228173, 499681507, 500251903, 550503457, 2101917261, 1135568167, 2083669856, 992855575, 1041748678, 2083199465, 184785149, 959837073, 2025874135, 1103028140, 582477025, 1878882487, 809686629, 1946678648, 835320212, 882326114, 1305497364, 632678922, 1046676267, 332528938, 230382393, 2049474593, 717717048, 2067470101, 273086001, 1456846153, 280223358, 889200557, 1761753757, 1602079663, 2075980952, 2119617991, 590629426, 608920218, 1970275095, 1243203015, 434541320, 1364342951, 256773240, 1834365418, 525367950, 1835543376, 772347915, 980907223, 2050618997, 1234591307, 1270615592, 234192250, 1755481145, 1963272614, 252999513, 959837073, 1248293543, 1188523862, 827875919, 650306001, 286328550, 1233057302, 21182638, 234185967, 1005283921, 1382414791, 1204744516, 353820494, 93909406, 1708194430, 1411122864, 191275689, 925959346, 1077715703, 524169037, 338142439, 1383946152, 1938052547, 2017618050, 158318873, 1283651019, 1002798106, 248312911, 108545779, 958124398, 810988877, 1206680576, 801064725, 1231532567, 1036750589, 672942133, 1228849520, 1271184549, 371031890, 2001388563, 2054638474, 405789612, 1539947824, 2143600882, 335919854, 287193693, 1083973675, 1579661247, 915635683, 399741236, 289683341, 1946725185, 1698216865, 542198534, 2097887691, 1046676267, 527911378, 650673972, 122182032, 1767572375, 189133073, 1583324432, 866269319, 307330271, 625859553, 1670940672, 1916913646, 325439108, 1113598166, 548280267, 2133347896, 1238318561, 942006131, 671117865, 1671433217, 1397369881, 1205529761, 2143449526, 979687467, 2084373316, 1681961637, 808465526, 568146809, 1706679679, 1364281340, 2067399680, 1800875007, 2079933713, 1717690867, 1074901997, 1635134078, 803115772, 719530340, 1261388047, 88803521, 997266633, 681327017, 640840106, 2142595036, 1953534753, 25167384, 306853686, 1527921091, 856340308, 1682279037, 1672425171, 1700899364, 1265510028, 1706364724, 1914183580, 328894035, 596370481, 331047763, 258122431, 359948522, 593199673, 1418396975, 1362302859, 573894609, 524169037, 245268044, 37683750, 425279855, 2085689501, 2113359811, 1107619873, 915273719, 1760527776, 1826480243, 196598673, 1767853591, 440231801, 418226586, 548280267, 500691908, 1734515375, 839897378, 310702305, 1095687519, 750241107, 1454839130, 1263298755, 2081400687, 1473175110, 1133509292, 180663141, 389161685, 1660360631, 1362476595, 88290438, 338142439, 2044556928, 1382497496, 1518213560, 74793912, 416286878, 557831566, 545368663, 362543248, 1338436466, 1201275221, 903572390, 721704302, 378274606, 731471225, 888602298, 1340045982, 518814904, 1885965404, 1117033075, 440231801, 1355598578, 486954654, 1483328308, 617719969, 1735004505, 750826293, 1233057302, 1908998721, 419793410, 599967314, 1048758132, 1782116234, 685470560, 686702452, 732572932, 740739813, 1162356721, 1282708948, 1537370981, 196422769, 358103497, 1487418944, 78714454, 1368196138, 633193961, 268970938, 569016291, 1399558106, 549074999, 1034503334, 1622631246, 1811084840, 123310019, 1270615592, 1554624323, 822686065, 959487304, 1034503334, 962082753, 764235441, 1904415891, 753962400, 1351394610, 335001283, 319668703, 1292070009, 1269343244, 244683660, 939977907, 1685783349, 1542896858, 1432146815, 771995861, 1757701636, 721704302, 1723117227, 1865170382, 1234718744, 398977496, 728904644, 1737942445, 472797321, 1607302145, 1791178392, 2118039687, 95898038, 942006131, 292390521, 1041748678, 161070481, 472338294, 2023692229, 429941664, 368910908, 291807980, 933753982, 681327017, 361856386, 97928048, 238323671, 883908018, 1580060586, 749641646, 2145803262, 595255670, 996409360, 840343146, 1956735510, 1545669143, 1999828290, 2121315996, 1523987634, 359750619, 1137681709, 1828888563, 537077189, 1679105630, 1094065633, 1750226398, 199382152, 1602437445, 1895949995, 140736874, 1015903193, 992855575, 426649736, 1411585041, 141937112, 1042331017, 1037616788, 450163221, 957650085, 296620453, 1357190850, 1566714917, 1325194608, 272151751, 1351394610, 703886873, 329314546, 1016796780, 633327842, 1018192457, 740896097, 2095995649, 1804686773, 1315420570, 524248911, 1904155145, 1306134223, 1319464401, 1733253101, 1396884988, 2105838458, 83304406, 1447686237, 1735185224, 743808137, 1158359413, 1162775366, 506409043, 1496918515, 996623389, 1632349255, 1912533912, 1878339486, 1195416317, 869492957, 1914183580, 629945856, 58654919, 591266985, 1596807024, 1291286760, 1300391206, 719583163, 991950937, 801723862, 1208633975, 2126524878, 1147042578, 434967654, 2078928603, 363079436, 1072335882, 856340308, 1090499079, 341872522, 530959399, 158318873, 921817678, 160070368, 1859078996, 847825210, 532299899, 2115076912, 970479397, 638089950, 1306445479, 1019066051, 116607368, 1447686237, 748599054, 1665245194, 1569187021, 858974514, 811077462, 1333945399, 482273390, 1970698613, 616511448, 615702125, 524248911, 119437024, 760002861, 1550482403, 467923590, 10686441, 400658276, 1187751294, 297800446, 991749800, 1223783533, 852747366, 1236862663, 92676722, 1218185218, 1660502484, 2113641418, 1964091132, 497709030, 1496918515, 1593772889, 620623299, 1509187955, 134529801, 1988119494, 1621936784, 1239627543, 773026832, 939097123, 2065585196, 2127509839, 421164797, 1628918914, 324979793, 345143437, 136033084, 141972027, 263003590, 1714179101, 1675938272, 1311786019, 644419809, 585376768, 1591465824, 1790166079, 926096033, 25172241, 1960970858, 1274630347, 642036475, 240606866, 644419809, 1030589043, 332528938, 145058805, 1291211056, 92676722, 468820279, 2088381338, 616203666, 657447605, 782561739, 699408806, 951380020, 1110076823, 459200749, 2090006544, 1698757835, 1139307142, 297540100, 284891577, 600977316, 673631460, 35740529, 986703790, 587320041, 1355598578, 985865213, 78209718, 535399523, 768710633, 523488422, 71356786, 256663046, 1126587027, 1951374748, 1449275702, 2056381598, 2060724858, 1256600986, 1633777983, 1798892449, 1975060060, 197339965, 1675938272, 1471137299, 1011217885, 1875742954, 1886819148, 933528259, 950756568, 861780118, 412569264, 992890050, 931678638, 752669214, 221013942, 486954654, 1213904593, 2004228524, 162176695, 1343540831, 1056851669, 2137181293, 1924532149, 366897022, 118420760, 528124516, 1980106071, 2079290811, 1772062880, 1349888499, 518362376, 1444730562, 963461718, 790323970, 1401665198, 592869471, 1032459806, 407154938, 1844691597, 1974306612, 2007287390, 123310019, 1307552366, 1939584521, 1067819891, 824422601, 444549833, 1248785289, 359983009, 592869471, 1688738109, 2081373870, 829939889, 37046771, 1929354053, 1229158282, 936087306, 1971864586, 54894678, 923674491, 1365711003, 671543353, 1691759934, 331555829, 18307937, 889792282, 1594316734, 2093456594, 1753989954, 646017396, 679486130, 1587354907, 160740908, 854672462, 2058551894, 1587174009, 543968257, 1805485695, 1511679135, 789445017, 1704598013, 453148571, 154822930, 766249601, 1818255155, 303661871, 169610119, 1665066176, 1502412774, 1076007434, 307330271, 1797937840, 727290358, 1636672122, 617170470, 487689085, 1879528483, 210582579, 622671468, 306853686, 1947081405, 689107975, 930986510, 240289951, 677056803, 91496837, 1394172341, 270823204, 1834140620, 239650766, 754698179, 1311580879, 113773003, 233414883, 629613342, 160260605, 899384205, 942163484, 738467374, 341083512, 1505389493, 1632958186, 272512753, 380749810, 24859467, 239628966, 890966218, 551276231, 1083265348, 1225009754, 1311786019, 90120712, 1004183235, 736915210, 968397899, 1834316462, 1078541512, 787424409, 270823204, 1878277601, 718296482, 1008226719, 322876067, 1881920118, 1641368286, 1261433119, 1514427983, 790151726, 1688515393, 1090499079, 766898965, 343229265, 1194172034, 1437471375, 483636114, 735836075, 2090523966, 787424409, 14164829, 97342142, 450163221, 1349376117, 698880388, 904924639, 1879999058, 301216582, 1543674834, 933753982, 1851576207, 1053405982, 1951271101, 590883438, 616093002, 129649389, 770280710, 1030686481, 113675998, 1282708948, 2003272511, 848545917, 1338087899, 1908041391, 1184638371, 745862339, 973314056, 1269617585, 1857557708, 518362376, 579329924, 2139999934, 201890473, 1248519349, 1136748142, 82073308, 1118590297, 1126587027, 150490834, 1556555846, 939520654, 19137408, 1604376983, 1671147232, 568669708, 477247649, 713672901, 1618021623, 1238652484, 923679922, 1363924170, 1706182101, 1270222870, 2129184081, 181031220, 582910489, 1334034467, 426649736, 1417013841, 1822527197, 1089514566, 380349092, 1439861510, 1840179201, 1401665198, 1001064628, 1411122864, 1198593322, 1072185424, 1195046996, 1868337719, 846179692, 244683660, 2082543486, 803115772, 1729937875, 728904644, 326524541, 880309423, 320539453, 1338436466, 2117543578, 1561307592, 1404230738, 1600373394, 1811084840, 269751562, 1714986751, 1366951141, 1088610923, 261448822, 838119681, 1346002994, 1604627318, 1580060586, 1879999058, 945846833, 999991566, 558216453, 1705349252, 2097604982, 875380348, 968946055, 1720623212, 1263298755, 924342751, 233414883, 665681011, 1827417037, 1487418944, 1357999123, 866740870, 1556429477, 1844691597, 670741187, 1798892449, 533939972, 1711387613, 77482413, 431401920, 237735526, 629613342, 1386056278, 1859078996, 1909099149, 177821874, 183723589, 1460342150, 310378483, 1574120907, 1357999123, 1359705904, 2024620261, 127197577, 440098639, 258452072, 1793099888, 1118085381, 248312911, 2073741654, 1359245518, 1760527776, 1494527097, 1167970994, 1994783164, 83012416, 48165603, 2013031958, 419303855, 717609417, 1069199928, 389161685, 1782866195, 629945856, 736915210, 432580229, 267597008, 1603993802, 1194314226, 1125568125, 535399523, 1026928318, 716470693, 957417597, 1413707760, 323243085, 922426422, 1679105630, 1225683451, 1396804547, 2091897626, 1683782359, 1303448950, 1576441802, 1485811481, 1779052057, 764948555, 1599008760, 285024128, 1607235591, 1795222379, 1089514566, 1455684643, 88145971, 2121315996, 625859553, 2114319696, 1323664802, 882326114, 379991763, 523459333, 1393691518, 1891724238, 2075981479, 1431652882, 2028660000, 1696775122, 1985615226, 1026048961, 959487304, 118026439, 48522034, 1717918563, 292735214, 1934803291, 1720623212, 2144746235, 1251033895, 473060738, 1728534993, 142109411, 1435504072, 409574421, 1875749845, 1816566071, 1375081504, 1316357157, 567518169, 34081108, 764235441, 1676627757, 1973287659, 603388061, 1547390000, 409574421, 2134524630, 549155083, 510267675, 1799154706, 1186715334, 1684421755, 1323152131, 1211038064, 658422407, 240545952, 1959715134, 697552309, 1936745197, 246569842, 1010010937, 1975704947, 737039158, 359709640, 2068537336, 771010072, 1223783533, 1257033275, 1651666404, 841618321, 249062960, 1323664802, 116607368, 2004343984, 795800901, 1283254604, 1905457709, 1379323576, 849195623, 1594990750, 1340703404, 1644674512, 1144093133, 835682322, 102991889, 1321471874, 1077369963, 1550438867, 1906071809, 1932370017, 1095183875, 724133082, 356817122, 1256600986, 89012233, 1974306612, 810986047, 1221470109, 1356844070, 1170220406, 303031103, 641375036, 216088210, 2124071937, 1819720171, 249935548, 113220891, 1795516540, 256070957, 129909114, 561542830, 141937112, 1331444372, 416012800, 509715204, 855768173, 1034668070, 1526227772, 326524541, 1228612728, 1828157509, 1447686237, 2106366714, 158403416, 848545917, 1728533551, 757378897, 1644232819, 399606167, 414931324, 1750874168, 1647251866, 1261481503, 1138603746, 1681487778, 2056163926, 615702125, 628084195, 1957033790, 1102842106, 1866277049, 618428739, 1427628789, 1926927134, 1906923326, 97928048, 781251781, 1310925515, 1584121424, 1404230738, 25493886, 93158142, 388946128, 1923540173, 958124398, 25167384, 271782845, 1319464401, 1419545489, 829844668, 753947465, 1425586318, 214619324, 988963148, 1152339406, 1010928145, 1547556451, 987470597, 191275689, 1251373739, 1993316245, 561001559, 1646813814, 1175464638, 1507259953, 1667146980, 1194172034, 215682822, 259034488, 188502069, 1241776351, 962654654, 1686023893, 923679922, 1210681866, 1092046035, 1888801182, 415985338, 5561448, 1153992036, 1689412633, 1969222382, 1537919837, 2127809895, 2073741654, 493084626, 377386929, 133687821, 2034932223, 201979455, 1932370017, 1365711003, 71014498, 570773690, 323147739, 1230641096, 1496155996, 887405876, 863714478, 896808506, 898937614, 1331444372, 1816566071, 1365211750, 1914610538, 883908018, 159245676, 240606866, 672975457, 543968257, 1769456284, 1915026764, 1608859846, 863600618, 1960554950, 961750267, 909059671, 1264298557, 1769456284, 694256689, 909059671, 99712434, 329506721, 1049578106, 691079513, 201126863, 1810894143, 1665297998, 1834140620, 1188209276, 449175565, 664796600, 661094088, 1258575394, 75045521, 1247216347, 366897022, 76405757, 1003141551, 291984552, 589352278, 2034758704, 1659934711, 1569187021, 6346180, 84757944, 371031890, 1210293707, 455432523, 2046662204, 741462593, 1773372283, 670449622, 361856386, 1248293543, 585376768, 632678922, 1689412633, 20893955, 858946596, 1556563216, 1929888017, 1666628509, 1933152779, 925309338, 1822527197, 71465821, 307875124, 386054492, 1604376983, 284891577, 319668703, 716781081, 1478356981, 463494602, 1502412774, 991363673, 1205529761, 1503566013, 365089823, 482369170, 1427722127, 1729190501, 500681523, 643884630, 810988877, 1283651019, 53206536, 279138325, 1731554158, 1342281711, 1433788673, 1003814176, 1910799299, 1433067572, 574669571, 1545889762, 1903908334, 2074085640, 492082850, 832822696, 1144128347, 726913652, 593372864, 1276871085, 266541344, 1516821127, 1684852678, 51942689, 2046342720, 1947081405, 2083958022, 494188454, 1443702350, 302847536, 740055996, 943904633, 221013942, 1072185424, 1941774667, 1571852620, 1452100523, 1362302859, 1085765563, 709260923, 384952692, 209746556, 664817425, 95898038, 1845991903, 920286748, 991200353, 147531315, 31749423, 1638832962, 1343540831, 369774785, 343730055, 1779052057, 1211038064, 100349633, 616912329, 1530663608, 247274314, 1536769976, 1031165880, 203560754, 507676957, 2055232873, 1332785199, 989634102, 1412919770, 1712663332, 2090374510, 1632958186, 1579703639, 1456695183, 11336464, 447793890, 1496155996, 1600103637, 1049624702, 1544220721, 1806988813, 388525603, 1688515393, 343730055, 903572390, 1033885955, 1864651677, 490333082, 1538150191, 1340977251, 620932879, 1633959263, 1210681866, 1228053553, 748599054, 1429190438, 452860596, 1463708231, 1160418779, 848587950, 78209718, 1438032980, 90549767, 590273265, 523245686, 2001388563, 1708003222, 970558419, 870944318, 1349036922, 1818255155, 826120529, 829380997, 479609697, 1241776351, 1805485695, 349696042, 1234591307, 1756558241, 832822696, 183749459, 936087306, 1746167885, 1947596891, 975911080, 1068212119, 1076913648, 309933752, 164551340, 2095133043, 1432146815, 1283254604, 1386056278, 1708520997, 231798475, 1563320665, 1858982453, 2106366714, 2097727245, 294380890, 528327465, 1411855029, 1745188664, 290573083, 963997310, 1583324432, 1990625570, 1483662604, 270743376, 284571817, 183771382, 747559042, 84405079, 1729937875, 180663141, 1193434274, 1766840193, 119437024, 885127795, 280491536, 48808513, 1193899165, 1138846091, 91066072, 1098192223, 2001461158, 720101928, 928566610, 70573173, 572365472, 823065319, 202961462, 1615138117, 2099588246, 472354443, 1252069834, 532061936, 1162358859, 1671923928, 650306001, 1512251088, 30455058, 1890830822, 2133347896, 299945134, 362720299, 359494534, 801064725, 327922866, 411719865, 48165603, 2127509839, 387459051, 202564793, 1285860224, 1020352934, 134168194, 1007928477, 85587158, 1996116400, 285043878, 188419003, 861989552, 2127583276, 2137570257, 1855698525, 1046676267, 1951271101, 1612994450, 142444800, 143506880, 1845991903, 1211216203, 1201702211, 1082907239, 840343146, 471578550, 1939646782, 514274459, 1728940556, 1536860934, 1900974837

    //int val = TT::singleNumber(nums);
    //vector<int> preorder = { 3, 9, 20, 15, 7 };
    //vector<int> inorder = { 9, 3, 15, 20, 7 };
    //TreeNode* p = TT::buildTree(preorder, inorder);

    //bool verifyPostorder(vector<int>&postorder)

    //TT::findContinuousSequence(9);

    //TreeNode t1(3), t2(5), t3(1), t4(6), t5(2), t6(0), t7(8), t8(7), t9(4);
    //t1.left = &t2; t1.right = &t3;
    //t2.left = &t4; t2.right = &t5;
    //t3.left = &t6; t3.right = &t7;
    //t5.left = &t8; t5.right = &t9;
    //TT::lowestCommonAncestor(&t1, &t2, &t3);

    //TT::lastRemaining(5, 3);

   
    //vector<int> nums{ 1, 2, 3, 2, 2, 2, 5, 4, 2 };
   // int ret = TT::majorityElement(nums);

    //TreeNode t1(3), t2(9), t3(20), t4(15), t5(7);
   // t1.left = &t2; t1.right = &t3;
    //t3.left = &t4; t3.right = &t5;
    //bool bRet = TT::isBalanced(&t1);

    //ListNode head(1);
    //TT::rotateRight(&head, 5);

    //string s = " 1";
    //string ss = TT::reverseWords(s);

   // vector<vector<int>> vec{ {1,3},{6,9} };
   // vector<int> tt{ 2,5 };
   //int count = TT::movingCount(7, 2, 3);

    //vector<vector<char>> matrix{ {'A'}};
    //string word = "A";
    //bool bRet = TT::exist(matrix, word);
    //string s = " 1";
    //string ss = TT::reverseWords(s);

    //vector<vector<int>> vec{ {1,3},{6,9} };
    //vector<int> tt{ 2,5 };
    //vector<vector<int>> out = TT::insert(vec, tt);

    //vector<int> nums{ 1,3,5,11,17 };
    //nums = TT::exchange(nums);

    //vector<int> ages{ 109,6,101,18,13,20,106,110,110,108,55,89,81,56,84,37,71,51,88,70,27,16,31,63,99,68,12,120,104,18,110,42,93,106,99,63,3,82,22,17,69,49,88,117,57,37,95,15,50,18,77,103,102,104,87,1,23,97,93,15,9,35,59,103,118,23,52,66,86,7,40,33,60,4,113,43,21,58,31,120,71,56,19,67,68,32,84,14,50,55,98,34,89,32,58,20,93,37,95,40 };
    //int count = TT::numFriendRequests(ages);
 
   // using namespace Day20211220;
    {
        //56. 合并区间
        //vector<vector<int>> intervals{ {} };
        //vector<vector<int>> ret = merge(intervals);

        //vector<int> vec{ 0, 1, 3 };
        //int ret = LeetCode::Day20211220::missingNumber(vec);

        //vector<int> vec{ 3,4,5,3,3,3,3, };
        //int ret = LeetCode::Day20211220::minArray(vec);

        //string s = "itwqbtcdprfsuprkrjkausiterybzncbmdvkgljxuekizvaivszowqtmrttiihervpncztuoljftlxybpgwnjb";
        //char c = LeetCode::Day20211220::firstUniqChar(s);

       // [3, 9, 20, null, null, 15, 7]
        //TreeNode root(3), l1l(9), l1r(20), l2l(15), l24(7);
        //root.left = &l1l; root.right = &l1r;
        //l1r.left = &l2l; l1r.right = &l24;
        //vector<vector<int>> ret = LeetCode::Day20211220::levelOrder3(&root);


        //double ret = LeetCode::Day20211220::myPow(2.0, -10);
        /*
        TreeNode A1(3), A2(4), A3(5), A4(1), A5(2);
        TreeNode B1(4), B2(1);
        A1.left = &A2; A1.right = &A3; A2.left = &A4; A2.right = &A5;
        B1.left = &B2;
        bool bRet = TT::isSubStructure(&A1, &B1);
        */

        //TreeNode A1(4), A2(2), A3(7), A4(1), A5(3), A6(6), A7(9);
        //A1.left = &A2; A1.right = &A3; A2.left = &A4; A2.right = &A5; A3.left = &A6; A3.right = &A7;
        //TreeNode* t = TT::mirrorTree(&A1);

        //vector<int> nums{ 7,1,5,3,6,4 };
        //int ret = TT::maxProfit(nums);

        //ListNode head;
        //ListNode* ttt =TT::getKthFromEnd(&head, 1);
        //TreeNode t1(1), t2(10), t3(4), t4(3), t5(7), t6(9), t7(12), t8(8), t9(6), t10(2);
        //t1.left = &t2; t1.right = &t3;
        //t2.left = &t4;
        //t3.left = &t5; t3.right = &t6;
        //t4.left = &t7; t4.right = &t8;
        //t5.left = &t9;
        //t6.right = &t10;
        //bool b = TT::isEvenOddTree2(&t1);

       // int iRet = TT::orchestraLayout(5, 2, 2);

        //int i = 0;
        //i = i;
    }

    //vector<vector<int>> richer{ {1, 0},{2, 1}, {3, 1},{3, 7},{4, 3},{5, 3},{6, 3} };
    //vector<int> quite{ 3,2,5,4,6,1,7,0 };
    //vector<int> ss = LeetCode::loudAndRich(richer, quite);

    
    //LeetCode::ListNode n1(1), n2(2), n3(3), n4(4),n5(5);
    //n1.next = &n2; n2.next = &n3; n3.next = &n4; n4.next = &n5;
    //LeetCode::ListNode* ret = LeetCode::swapPairs(&n1);
    //ret = ret;
    //vector<int> nums{ 1,2,5,3,4 };
    //LeetCode::nextPermutation(nums);

    //vector<int> nums{ 1,3};
    //int ret = LeetCode::search(nums,0);

    //vector<int> nums{ 2,2 };
    //LeetCode::searchRange(nums, 3);

    /*
    vector<vector<char>> board{
        {'5', '3', '.', '.', '7','.', '.', '.', '.'},
        {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
        {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
        {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
        {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
        {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
        {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
        {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
        {'.', '.', '.', '.', '8', '.', '.', '7', '9'} };
        
    LeetCode::isValidSudoku(board);
    */

    //string ss = LeetCode::getHint("1899077", "5810999");

    //vector<int> nums{ 2, 3, 1, 1, 4 };
    //bool b = LeetCode::canJump(nums);

    /*
    vector<int> nums{ 17,18,5,4,6,1 };
    vector<int> ret = LeetCode::replaceElements(nums);
    */

    //LeetCode::ListNode n1(1), n2(2), n3(3), n4(4), n5(5), n6(6), n7(7);
    //n1.next = &n2; n2.next = &n3; n3.next = &n4; n4.next = &n5; n5.next = &n6;// n6.next = &n7;
    //LeetCode::ListNode *ret = reverseKGroup(&n1, 2);

    /*
    LeetCode::Node h1(7), h2(13),h3(11),h4(10),h5(1);
    h1.next = &h2; h1.random = nullptr;
    h2.next = &h3; h2.random = &h1;
    h3.next = &h4; h3.random = &h5;
    h4.next = &h5; h4.random = &h5;
    h5.next = nullptr; h5.random = &h3;
    LeetCode::Node* retHead = LeetCode::copyRandomList(&h1);
    */

    //LeetCode::hammingWeight(11);

    //LeetCode::myPow(2.0, 10);

    //int ret = LeetCode::movingCount(1, 2, 1);

    //vector<vector<char>> board = { {'A','B','C','E'},{'S','F','E','S'},{'A','D','E','E'} };
    //LeetCode::exist(board, "ABCESEEEFS");

    //剑指 Offer 31. 栈的压入、弹出序列
    //vector<int> pushed{ 0,2,1 };
    //vector<int> popped{ 0,1,2 };
    //LeetCode::validateStackSequences(pushed, popped);
    //17. 电话号码的字母组合
    //string ss = "234";
    //vector<string> out = LeetCode::letterCombinations(ss);

    //vector<int> ss{ 1000000000,1000000000,1000000000,1000000000 };
    //vector<vector<int>> ret = LeetCode::fourSum(ss, 0);

    //47. 全排列 II
    //vector<int> nums = { -1, 2, -1, 2, 1, -1, 2, 1 };
    //vector<vector<int>> out = permuteUnique(nums);

    //45. 跳跃游戏 II
    //vector<int> nums = { 2,3,1,1,4 };
    //return jump(nums);


    //43. 字符串相乘
    /*
    string num1 = "0";
    string num2 = "456344";
    string ret= multiply(num1,num2);
    cout << num1 << "*" << num2 << "=" << ret;
    */

    //40. 组合总和 II
    //vector<int> candidates = { 3,1,3,5,1,1 };
    //vector<vector<int>> ret = combinationSum2(candidates, 8);

    //39. 组合总和
    //vector<int> candidates = { 2,3,6,7 };
    //vector<vector<int>> ret = combinationSum(candidates, 7);
    

    //33. 搜索旋转排序数组
    //vector<int> nums = { 2,3,6,7 };
    //int search(vector<int>&nums, int target);

    //33. 搜索旋转排序数组
    //vector<int> nums = { 5,6,7,8,9,1,2,3,4 };
    //int ret = search33(nums,1);
    //cout << ret << endl;

#pragma region 20210121
    //13罗马字符转换
    /*
    int ret = romanToInt("MCMXCVI");
    cout << ret << endl;
    */

    //14. 最长公共前缀
    /*
    vector<string> strs;
    strs.push_back("flower");
    strs.push_back("aflow");
    strs.push_back("flight");
    string ret = longestCommonPrefix(strs); 
    cout << ret << endl;
    */

    //20. 有效的括号
    /*
    string st = "([)]";
    bool bRet = isValid(st);
    */

    //21. 合并两个有序链表
    /*
    ListNode l1(5), l11(6), l12(7);
    ListNode l2(11), l21(13), l22(14);
    l1.next = &l11;
    l11.next = &l12;
    l2.next = &l21;
    l21.next = &l22;

    ListNode *pRet = mergeTwoLists(&l1, &l2);
    */

    //26. 删除排序数组中的重复项
    /*
    vector<int> nums = { 1,1, 2, 3, 4,4 ,5};
    int ret = removeDuplicates(nums);
    */
    
    //27. 移除元素
    /*
    vector<int> nums = { 1,1, 2, 3, 4,1,4 ,5,1 };
    int ret = removeElement(nums, 1);
    */

    //28. 实现 strStr()
    /*
    string haystack = "cab", needle = "ab";
    int ret = strStr(haystack, needle);
    */

    //35. 搜索插入位置
    /*
    vector<int> nums = { 1,3,5,6 };
    int target = 0;
    int ret = searchInsert(nums, target);
    */

    //38. 外观数列
    /*
    string ret = countAndSay(5);
    */
#pragma endregion

#pragma region 20210122
    //53. 最大子序和
    /*
    vector<int> nums{-1,2,-7,20,0,5,-5,3,7};
    int ret = maxSubArray(nums);
    */

    //58. 最后一个单词的长度
    /*
    string str = "   ";
    int ret = lengthOfLastWord(str);
    */

    //66. 加一
    /*
    vector<int> src = {0,0,9,9,9 }, out;
    out = plusOne(src);
    */

    //67. 二进制求和
    /*
    string a = "1010";
    string b = "10";
    string strRet  =addBinary(a,b);
    */

    //69. x 的平方根
    /*
    int x = 150;
    int ret = mySqrt(x);
    */

    //70. 爬楼梯
    /*
    int n = 10;
    int ret = climbStairs(n);
    */

    //83. 删除排序链表中的重复元素
    /*
    ListNode l1(5), l11(6), l12(7),l13(7),l14(7),l15(9);
    l1.next = &l11;
    l11.next = &l12;
    l12.next = &l13;
    l13.next = &l14;
    l14.next = &l15;
    ListNode* pRet = deleteDuplicates(&l1);
    */

    //88. 合并两个有序数组
    /*
    vector<int> nums1 = { 1,2,5,6,9,10 };
    vector<int> nums2 = {};
    merge(nums1, 6, nums2, 0);
    */
    
    //100. 相同的树
    /*
    TreeNode* p = new TreeNode(1), * pl1 = new TreeNode(2), * pr1 = new TreeNode(3);
    p->left = pl1;
    p->right = pr1;
    TreeNode *q = new TreeNode(1),*ql1 = new TreeNode(2), *ql2 = new TreeNode(3);
    q->left = ql1;
    ql1->left = ql2;

    bool bRet = isSameTree(p, q);
    */

    //101. 对称二叉树
    /*
    TreeNode* root;
    bool ret = isSymmetric(root);
    */

    //104. 二叉树的最大深度
    /*
    TreeNode root(1), l1(1), l2(2), l3(3), l4(4), l5(5), l6(6);
    root.left = &l1;
    root.right = &l2;
    l1.left = &l3;
    l1.right = &l4;
    l4.left = &l6;
    l2.left = &l5;
    int ret = maxDepth(&root);
    */
#pragma endregion

#pragma region 20210123
    //107. 二叉树的层序遍历 II
    /*
    TreeNode root(0), l1(1), l2(2), l3(3), l4(4), l5(5);
    root.left = &l1;
    root.right = &l2;
    l1.left = &l3;
    l3.right = &l4;
    l2.left = &l5;
    vector<vector<int>> out =  levelOrderBottom(&root);
    */

    //108. 将有序数组转换为二叉搜索树
    /*
    vector<int> nums = { -10,-3,0,5,9 };
    TreeNode* ret = sortedArrayToBST(nums);
    */

    //110. 平衡二叉树
    /*
    TreeNode root(0),l1(1),l2(2),l3(3),l4(4),l5(5),l6(6);
    root.left = &l1;
    root.right = &l2;
    l1.left = &l3;
    l1.right = &l4;
    l2.left = &l5;
    l2.right = &l6;
    bool bRet = isBalanced(&root);
    */

    //111. 二叉树的最小深度
    /*
    TreeNode root(0), l1(1), l2(2), l3(3), l4(4), l5(5), l6(6);
    root.left = &l1;
    root.right = &l2;
    l1.left = &l3;
    l1.right = &l4;
    l2.left = &l5;
    l5.right = &l6;
    int ret = minDepth(&root);
    */

    //112. 路径总和
    /*
    TreeNode root(0), l1(1), l2(2), l3(3), l4(4), l5(5), l6(6);
    root.left = &l1;
    root.right = &l2;
    l1.left = &l3;
    l1.right = &l4;
    l2.left = &l5;
    l5.right = &l6;
    bool ret = hasPathSum(&root,10);
    */

    //118. 杨辉三角 
    /*
    int numRows = 5;
    vector<vector<int>> ret = generate(numRows);
    */

    //119. 杨辉三角 II
    /*
    int rowIndex = 3;
    vector<int> out = getRow(rowIndex);
    */

    //121. 买卖股票的最佳时机    
    /*
    vector<int> prices = { 17,1,5,3,6,4 };
    int ret = maxProfit(prices);
    */

    //125. 验证回文串
    /*
    string s = "A man, a plwewe: Panama";
    bool ret = isPalindrome(s);
    */

    //141. 环形链表
    /*
    ListNode head(3),l1(2),l2(0),l3(4);
    head.next = &l1;
    l1.next = &l2;
    l2.next = &l3;
    l3.next = &l1;
    bool ret = hasCycle(&head);
    */
#pragma endregion

#pragma region 20210126
    //155. 最小栈
/*
    MinStack minStack;
    minStack.push(2147483646);
    minStack.push(2147483646);
    minStack.push(2147483647);
    cout << minStack.top() << endl;
    minStack.pop();
    cout << minStack.getMin() << endl;   
    minStack.pop();
    cout << minStack.getMin() << endl;  // -- > 返回 - 2
    minStack.pop();
    minStack.push(2147483647);
    cout << minStack.top() << endl;
    cout << minStack.getMin() << endl;  // -- > 返回 - 2
    minStack.push(-2147483648);
    cout << minStack.top() << endl;      //-- > 返回 0.
    cout << minStack.getMin() << endl;
    minStack.pop();
    cout << minStack.getMin() << endl;  // -- > 返回 - 2
*/
    //160. 相交链表
    /*
    ListNode a1(4), a2(6), a3(1), a4(8), a5(4);
    ListNode b1(11), b2(1);
    a1.next = &a2;
    a2.next = &a3;
    a3.next = &a4;
    a4.next = &a5;
    b1.next = &b2;
    b2.next = &a4;
    ListNode* ret = getIntersectionNode(&a1, &b1);
    */
    
    //167. 两数之和 II - 输入有序数组
    /*
    vector<int> src = { 1,2,3,4,5,8,11 };
    vector<int> ret = twoSumII(src, 11);
    */

    //168. Excel表列名称
    /*
    string  ret = convertToTitle(52);    
    cout << ret << endl;
    */

    //169. 多数元素
    /*  
    vector<int> nums = { 2,3,3,2,4,3,3 };
    int ret = majorityElement(nums);
    */
#pragma endregion

#pragma region 20210127
    //171. Excel表列序号
    /*
    string s = "AB";
    int ret = titleToNumber(s);
    */

    //172. 阶乘后的零
    //int ret = trailingZeroes(10);

    //190. 颠倒二进制位
    //uint32_t ret = reverseBits((uint32_t)10);

    //202. 快乐数
    //bool ret = isHappy(9);

    //203. 移除链表元素
    /*
    ListNode n1(1), n2(2), n3(3), n4(4), n5(5), n6(6);
    n1.next = &n2;
    n2.next = &n3;
    n3.next = &n4;
    n4.next = &n5;
    n5.next = &n6;
    ListNode* ret = removeElements(&n1,6);
    */

    //204. 计数质数
    //int ret = countPrimes(10);

    //204. 计数质数
    //int ret = countPrimes(20);

    //205. 同构字符串
    //bool ret = isIsomorphic("eggabcd","addbcde");

    //206. 反转链表
    /*
    ListNode n1(1), n2(2), n3(3), n4(4), n5(5), n6(6);
    n1.next = &n2;
    n2.next = &n3;
    n3.next = &n4;
    n4.next = &n5;
    n5.next = &n6;
    ListNode* head = reverseList(&n1);
    */

    //217. 存在重复元素
    //vector<int> nums;
   // bool ret = containsDuplicate(nums);

    //219. 存在重复元素 II
    //vector<int> nums ={ 1,2,3,4,1 };
    //bool ret = containsNearbyDuplicate(nums, 3);

    //226. 翻转二叉树
    //TreeNode root(0);
    //TreeNode* ret = invertTree(&root);

    //228. 汇总区间
    //vector<int> nums = { -2,-1,0,2,4,8,9 };
    //vector<string> ret = summaryRanges(nums);

    //231. 2的幂
    //bool ret = isPowerOfTwo(1024);

    //232. 用栈实现队列
    /*
    MyQueue myQue;
    myQue.push(1);
    myQue.push(2);
    myQue.push(3);
    myQue.push(4);
    cout << myQue.peek() << endl;
    cout << myQue.pop() << endl;
    cout << myQue.pop() << endl;
    cout << myQue.peek() << endl;
    cout << myQue.empty() << endl;
    */
    
    //234. 回文链表
    /*
    ListNode n1(0),n2(1),n3(0);
    n1.next = &n2;
    n2.next = &n3;
    bool ret = isPalindrome(&n1);
    Solution s;
    s.isPalindrome(&n1);
    */

    //235. 二叉搜索树的最近公共祖先
    /*
    TreeNode root(6),n2(2),n0(0),n4(4),n3(3),n5(5),n7(7),n8(8),n9(9);
    root.left = &n2;
    root.right = &n8;
    n2.left = &n0;
    n2.right = &n4;
    n4.left = &n3;
    n4.right = &n5;
    n8.left = &n7;
    n8.right = &n9;
    TreeNode* ret = lowestCommonAncestor(&root,&n2,&root);
    */

    //237. 删除链表中的节点
    /*
    ListNode n1(0), n2(1), n3(0);
    n1.next = &n2;
    n2.next = &n3;
    deleteNode(&n2);
    */
#pragma endregion

#pragma region 20210207
    //242. 有效的字母异位词
    //string s = "adss", t = "ssda";
    //cout << isAnagram(s, t) << endl;

    //257. 二叉树的所有路径
    /*
    TreeNode root(6), n2(2), n0(0), n4(4), n3(3), n5(5), n7(7), n8(8), n9(9);
    root.left = &n2;
    root.right = &n8;
    n2.left = &n0;
    n2.right = &n4;
    n4.left = &n3;
    n4.right = &n5;
    n8.left = &n7;
    n8.right = &n9;
    vector<string> ret = binaryTreePaths(&root);

    for (auto it : ret)
        cout << it << endl;
    */
    
    //258. 各位相加
    //int ret = addDigits(5555);

    //263.编写一个程序判断给定的数是否为丑数。
    //cout << isUgly(15);

    //278. 第一个错误的版本
    //cout << firstBadVersion(5);

    //268. 丢失的数字
    /*
    vector<int> nums = { 4,1,2,3,0 };
    cout << missingNumber(nums);
    */

    //283. 移动零
    /*
    vector<int> nums = { 1 };
    moveZeroes(nums);
    */

    //290. 单词规律
    //cout << wordPattern("abba", "dog dog dog dog");

    //292. Nim 游戏
    //cout<< canWinNim(20);

    //326. 3的幂
    //cout<< isPowerOfThree(300);

    //344. 反转字符串
    /*
    vector<char> s = { 'a','b','e','c','d' };
    reverseString(s);
    */

    //345. 反转字符串中的元音字母
    /*
    string s = "hello";
    cout << reverseVowels(s);
    */

    //349. 两个数组的交集
    /*
    vector<int> nums1 = { 1,2,3,4,5,0,2,2,4,5,6 };
    vector<int> nums2 = { 1,2,3,4 };
    intersection(nums1, nums2);
    */

#pragma endregion

#pragma region 20210209
    //350. 两个数组的交集 II
    /*
    vector<int> src1 = { 4,9,4,5};
    vector<int> src2 = {9,4,9,8,4};
    vector<int> ret = intersect(src1, src2);
    */

    //367. 有效的完全平方数
    //cout << isPerfectSquare(2147483647);

    //383. 赎金信
    //cout << canConstruct("aa", "ab");

    //387. 字符串中的第一个唯一字符
    //string s = "lleetcode";
    //cout << firstUniqChar(s);

    //389. 找不同
    //cout << "多余的字符:" << findTheDifference("aadsd", "aadsda");

    //392. 判断子序列
    //cout << "判断子序列:" << isSubsequence("ace", "acede");

    //401. 二进制手表
    /*
    vector<string> vecStr;
    vecStr = readBinaryWatch(9);
    cout << "二进制手表:" << endl;
    */

#pragma endregion

#pragma region 20210210
    //404. 左叶子之和
    /*
    TreeNode root(3),l1(9),l2(2),l3(15),l4(7),l5(9);
    root.left = &l1;
    root.right = &l2;
    l2.left = &l3;
    l2.right = &l4;
    l4.left = &l5;
    cout << "左叶子之和" << sumOfLeftLeaves(&root);
    */

    //405. 数字转换为十六进制数
    //cout << "数字转换为十六进制数:" << toHex(16);

    //409. 最长回文串
    //cout << "最长回文串:" << longestPalindrome("ccc");

    //412. Fizz Buzz
    //vector<string> vec = fizzBuzz(100);

    //414. 第三大的数
    //vector<int> nums = { 2,2,3,1 };
    //cout << thirdMax(nums);

    //415. 字符串相加
    //cout << "字符串相加" << addStrings("99999999", "99");

    //434. 字符串中的单词数
    //cout << "字符串中的单词数:" << countSegments("   sfdsf adfa   adsfad adfaf    adsf   ");

    //441. 排列硬币
    //cout << "排列硬币:" << arrangeCoins(20);

    //448. 找到所有数组中消失的数字
    //vector<int> nums = { 2,3,3,1,5,5,5,6,7 };
    //vector<int> out = findDisappearedNumbers(nums);

    //453. 最小操作次数使数组元素相等
    //vector<int> nums = { 1,2,3,4,5 };
    //cout << minMoves(nums);

    //455. 分发饼干
    /*
    vector<int> vecg  ={ 2,2,3 };
    vector<int> vecs = { 1,1};
    cout << findContentChildren(vecg, vecs);
    */
#pragma endregion

#pragma region 20210214
//461. 汉明距离
//cout << hammingDistance(0,4);

//463. 岛屿的周长
/*
vector<vector<int>> grid;
vector<int> a = { 0,1,0,0 };
vector<int> b = { 1,1,1,0 };
vector<int> c = { 0,1,0,0 };
vector<int> d = { 1,1,0,0 };
grid.push_back(a);
grid.push_back(b);
grid.push_back(c);
grid.push_back(d);
cout<<islandPerimeter(grid);
*/

//476. 数字的补数
//cout << findComplement(0);

//482. 密钥格式化
//cout << licenseKeyFormatting("---", 3);

//485. 最大连续1的个数
//vector<int> nums = { 1,2,3,3,3,4,4,4,4,5,5,1,1,1 };
//cout << findMaxConsecutiveOnes(nums);

//492. 构造矩形
//constructRectangle(4);

//496. 下一个更大元素 I
/*
vector<int> nums1 = { 4,1,2 };
vector<int> nums2 = { 1, 3, 4, 2 };
nextGreaterElement(nums1, nums2);
*/

//501. 二叉搜索树中的众数
/*
TreeNode root(5), r1l(3), r1r(6), r2l(1), r2r(3), r3r(5), r4r(6), r5r(7);
root.left = &r1l;
root.right = &r1r;
r1l.left = &r2l;
r1l.right = &r2r;
r1r.left = &r3r;
r1r.right = &r4r;
r4r.right = &r5r;
vector<int> ret = findMode(&root);
for (auto it : ret)
cout << it << ",";
*/

//504. 七进制数
//cout << convertToBase7(100);

//506. 相对名次
/*
    vector<int> score = { 1,2,3,5,4,12,44,32,56,78,34 };
    vector<string> ret = findRelativeRanks(score);
    for (auto it : ret)
        cout << it << ",";
*/

//507. 完美数
    //cout << checkPerfectNumber(28);

//509. 斐波那契数
    //cout << fib(10);

//520. 检测大写字母
    //cout << detectCapitalUse("LEetcode");
#pragma endregion

    //530.二叉搜索树的最小绝对差
    /*
    TreeNode root(236), r1(104), r2(701),r3(227),r4(911);
    root.left = &r1;
    root.right = &r2;
    r1.right = &r3;
    r2.right = &r4;    
    cout<< getMinimumDifference(&root);
    */

    //541. 反转字符串 II
    //cout << reverseStr("abcdefghijklmnopqrs", 4);

    //543. 二叉树的直径
/*
    TreeNode root(0), r1(1), r2(2), r3(3), r4(4), r5(5), r6(6), r7(7), r8(8), r9(9);
    root.left = &r1;
    root.right = &r2;
    r1.left = &r3;
    r1.right = &r4;
    r3.left = &r5;
    r3.right = &r6;
    r4.right = &r7;
    r7.right = &r8;
    r8.right = &r9;
    cout<< diameterOfBinaryTree(&root);
 */    

    //551. 学生出勤记录 I
    //cout << checkRecord("APPLLAPPLPLA");

    //557. 反转字符串中的单词 III
    //cout << reverseWords("xiao jie leetcode master");

    //561. 数组拆分 I
    //vector<int> nums = { 0,1,2,2,3,4,5,6,7,8,4,3 };
    //cout << arrayPairSum(nums);
    
    //563. 二叉树的坡度
    /*
    TreeNode root(0), r1(1), r2(2), r3(3), r4(4), r5(5), r6(6), r7(7);
    root.left = &r1;
    root.right = &r2;
    r1.left = &r3;
    r1.right = &r4;
    r2.left = &r5;
    r5.left = &r6;
    r6.right = &r7;
    cout<< findTilt(&root);
    */

    //566. 重塑矩阵
    /*
    vector<int> a = { 1,2,5 };
    vector<int> b = { 3,4,6};
    vector<vector<int>> nums;
    nums.push_back(a);
    nums.push_back(b);
    matrixReshape(nums, 3, 2);
    */

    //575.分糖果
    //vector<int> nums = { 1,1,2,2,3,3,4,5 };
    //cout<< distributeCandies(nums);

    //643. 子数组最大平均数 I
    //vector<int> nums = { 1,12,-5,-6,50,3 };
    //double ret = findMaxAverage(nums, 4);

    //867. 转置矩阵
    /*
    vector<vector<int>> vec;
    vec.push_back(vector<int>{1, 2, 3, 4, 5, 6, 7, 8, 9});
    vec.push_back(vector<int>{1, 2, 3, 4, 5, 6, 7, 8, 9});
    vec.push_back(vector<int>{1, 2, 3, 4, 5, 6, 7, 8, 9});
    vec.push_back(vector<int>{1, 2, 3, 4, 5, 6, 7, 8, 9});
    vector<vector<int>> ret = transpose(vec);
    */

    //1178. 猜字谜
    /*
    vector<string> words= { "aaaa", "asas", "able", "ability", "actt", "actor", "access" };
    vector<string> puzzles = { "aboveyz", "abrodyz", "abslute", "absoryz", "actresz", "gaswxyz" };
    vector<int> ret = findNumOfValidWords(words, puzzles);
    */

    //31. 下一个排列
    //vector<int> nums = { 3,2 ,1};
    //nextPermutation(nums);

    //32. 最长有效括号
    //cout << longestValidParentheses("()(()");

    //395. 至少有K个重复字符的最长子串
    //cout << longestSubstring("aaaaaaaaabbbcccccddddd",5);

    //
    //450. 删除二叉搜索树中的节点
/*
    TreeNode r0(0),r1(-10),r2(10),r3(-20),r4(-5),r5(20),r6(6);
    r0.left = &r1;
    r0.right = &r2;
    r1.left = &r3;
    r1.right = &r4;
    r2.left = &r6;
    r2.right = &r5;
    TreeNode* root = deleteNode(&r0, 0);
    */

    //46.全排列
    /*
    vector<int> a{ 1,2,3,4 };
    vector<vector<int>> ret = permute(a);
    for (auto it1 : ret)
    {
        string ss = "[";
        for (auto it2 : it1)
        {
            ss += std::to_string(it2);
            ss += ",";
        }
        ss += "]";

        cout << ss << endl;
    }
    */

    //328. 奇偶链表
    /*
    ListNode head(1), h2(2), h3(3), h4(4),h5(5),h6(6),h7(7);
    head.next = &h2;
    h2.next = &h3;
    h3.next = &h4;
    h4.next = &h5;
    h5.next = &h6;
    h6.next = &h7;
    ListNode* hh = oddEvenList(&head);

    while(hh)
    {
        cout << hh->val << ",";
        hh = hh->next;
    }
    */

    //面试题 02.08.环路检测
    /*
    ListNode h1(3), h2(2), h3(4), h4(5);
    h1.next = &h1;
    h2.next = &h3;
    h3.next = &h4;
    h4.next = &h2;
    ListNode* hh = detectCycle(&h1);
    */

    return 0;


#pragma region 其它验证
    //堆排序
    //vector<int> nums = { 0,1,2,4,5,11,2,44,23,4,5,32,1 };
    //HeapSort(nums);

   // vector<int> vec;
   // vec.push_back(1);
   // vec.push_back(2);
   // vec.push_back(3);
   // vec.push_back(4);
   // 
   // deque<int> st;
   // st.push_back(1);
   // st.push_back(2);
   // st.push_front(0);
   // st.push_front(-1);


   // map<int,int> m;
   // forward_list<int> f;
   // f.push_front(1);
   // f.pop_front();
   // f.front();

    /*
    unordered_set<int> umap;
    std::pair<std::unordered_set<int>::iterator, bool> it;
    for (int i = 0; i < 10; i++)
    {
        it = umap.insert(i);
        if (it.second)
            cout << "(" << i << ")插入成功" << endl;
        else
            cout << "(" << i << ")插入失败" << endl;

        it = umap.insert(i+1);
        if (it.second)
            cout << "(" << i+1 << ")插入成功" << endl;
        else
            cout << "(" << i+1 << ")插入失败" << endl;
    }

    cout << "输出：" << endl;
    for (auto it1 : umap)
    {
        cout << it1<< endl;
    }

    auto it1 = umap.find(0);
    cout << *it1 << endl;
    */

#pragma endregion
    
#pragma region 排序算法
    //vector<int> nums = { 11,2,14,3,5,2,8,11,34,1,26,0,3432,55,104,12,1 };
    
    //冒泡排序
    //BubbleSort(nums);

    //快速排序
    //QuickSort(nums, 0, nums.size() - 1);

    //选择排序
    //SelectSort(nums);

    //插入排序
    //InsertSort(nums);

    //希尔排序
    //ShellSort(nums);

    //归并排序
    //MergeSort(nums, 0, nums.size() - 1);

    //计数排序
    //CountSort(nums);

    //桶排序
    //BucketSort(nums);

    //基数排序
    //RadixSort(nums);
#pragma endregion

#pragma region 数组指针或指针数组理解
/*
int m[4];           //数组
int* p[4];          //指针数组:一个数组，用来保存指针
int(*q)[4];         //数组指针:一个指针，该指针指向一个数组数组

int a = 1, b = 2, c = 3, d = 4;

m[0] = a;
m[1] = b;
m[2] = c;
m[3] = d;

p[0] = &a;
p[1] = &b;
p[2] = &c;
p[3] = &d;

int aa[4] = { 11,12,13,14 };
int bb[4] = { 22,23,24,25 };
int cc[4] = { 33,34,35,36 };
int dd[4] = { 43,44,45,46 };
int ee[4] = { 53,54,55,56 };
int ff[5] = { 53,54,55,56,57 };

cout << "m[0]地址:" << &m[0] << ",值:" << m[0] << endl;
cout << "m[1]地址:" << &m[1] << ",值:" << m[1] << endl;
cout << "m[2]地址:" << &m[2] << ",值:" << m[2] << endl;
cout << "m[3]地址:" << &m[3] << ",值:" << m[3] << endl;
cout << "***********************************" << endl;
cout << "p[0]地址:" << p[0] << ",值:" << *p[0] << endl;
cout << "p[1]地址:" << p[1] << ",值:" << *p[1] << endl;
cout << "p[2]地址:" << p[2] << ",值:" << *p[2] << endl;
cout << "p[3]地址:" << p[3] << ",值:" << *p[3] << endl;
cout << "***********************************" << endl;
cout << "a地址:" << &a << "值:" << a << endl;
cout << "b地址:" << &b << "值:" << b << endl;
cout << "c地址:" << &c << "值:" << c << endl;
cout << "d地址:" << &d << "值:" << d << endl;
cout << "***********************************" << endl;

q = &aa;
cout << "(*q[0])地址：" << &(*q)[0] << "，值：" << (*q)[0] << endl;
cout << "(*q[1])地址：" << &(*q)[1] << "，值：" << (*q)[1] << endl;
cout << "(*q[2])地址：" << &(*q)[2] << "，值：" << (*q)[2] << endl;
cout << "(*q[3])地址：" << &(*q)[3] << "，值：" << (*q)[3] << endl;
cout << "***********************************" << endl;
cout << "aa[0]地址：" << &aa[0] << "，值：" << aa[0] << endl;
cout << "aa[1]地址：" << &aa[1] << "，值：" << aa[1] << endl;
cout << "aa[2]地址：" << &aa[2] << "，值：" << aa[2] << endl;
cout << "aa[3]地址：" << &aa[3] << "，值：" << aa[3] << endl;
*/
#pragma endregion

#pragma region 算法验证
/*
int ia[5] = { 1,2,3,4,5 };

//用数组初始化vector
vector<int> iv(ia, ia + 5);
cout << std::accumulate(iv.begin(), iv.end(), 13) << endl;

cout << accumulate(iv.begin(), iv.end(), 10, minus<int>()) << endl;

cout << inner_product(iv.begin(), iv.end(), iv.begin(), 2) << endl;

cout << inner_product(iv.begin(), iv.end(), iv.begin(), 10, minus<int>(), plus<int>()) << endl;

ostream_iterator<int> oite(cout, "");
partial_sum(iv.begin(), iv.end(), oite);

vector<int> out;
//partial_sum(iv.begin(), iv.end(), out.begin());   ??why
cout << "*******************" << endl;
partial_sum(iv.begin(), iv.end(), oite, minus<int>());
cout << "*******************" << endl;
adjacent_difference(iv.begin(), iv.end(), oite);
cout << "*******************" << endl;
adjacent_difference(iv.begin(), iv.end(), oite, plus<int>());   
cout << "*******************" << endl;
cout << pow(10, 3) << endl;
cout << "*******************" << endl;
//cout<<std::power(10,3,)
//cout << pow(10, 3, plus<int>());
cout << "*******************" << endl;
int n = 3;
iota(iv.begin(), iv.end(), n);
for (auto it : iv)
cout << it << "  " << endl;
*/
#pragma endregion

#pragma region STL测试
/*
int ia[9] = { 0,1,2,3,4,5,6,7,8 };
vector<int> iv1(ia, ia + 5);
vector<int> iv2(ia, ia + 9);

//cout << *(mismatch(iv1.begin(), iv1.end(), iv2.begin()).first);
cout << *(mismatch(iv1.begin(), iv1.end(), iv2.begin()).second);

cout << equal(iv1.begin(), iv1.end(), iv2.begin());
cout << equal(iv1.begin(), iv1.end(), &ia[3]);
cout << equal(iv1.begin(), iv1.end(), iv2.begin()+3);
cout << equal(iv1.begin(), iv1.end(), &ia[3], less<int>());

swap(*iv1.begin(), *iv2.begin());
*/
#pragma endregion

#pragma region STL算法验证
/*
int ia[] = { 0,2,3,4,5,6,6,6,7,8 };
for_each(ia, ia + (sizeof(ia) / sizeof(int)), display<int>());
vector<int> iv(ia, ia + sizeof(ia) / sizeof(int));

//找出iv中相邻两个元素满足指定条件的第一个元素（默认是两元素相等，也可通过仿函数添加判断条件）
cout << *adjacent_find(iv.begin(), iv.end()) << endl;
cout << *adjacent_find(iv.begin(), iv.end(), equal_to<int>()) << endl;

//查找满足统计条件的元素值的个数
cout << count(iv.begin(), iv.end(), 6) << endl;                             //统计条件：值=6
cout << count_if(iv.begin(), iv.end(), bind2nd(less<int>(), 7)) << endl;    //统计条件：值小于7

//查找满足条件的第一个元素所在的位置
cout << *find(iv.begin(), iv.end(), 4) << endl;
cout << *find_if(iv.begin(), iv.end(), bind2nd(greater<int>(), 2)) << endl;

//查找iv1中和iv2匹配的最后一个匹配项
vector<int> iv2(ia + 6, ia + 8);
cout << *find_end(iv.begin(), iv.end(), iv2.begin(), iv2.end()) << endl;

//查找iv1中第一次出现iv2的位置
cout << *find_first_of(iv.begin(), iv.end(), iv2.begin(), iv2.end()) << endl;

//遍历区间，对每个元素实行指定操作
for_each(iv.begin(), iv.end(), [](int& i) { ++i; });   //每个元素+1
cout<< endl;
for_each(iv.begin(), iv.end(), display<int>());         //显示每个元素
cout << endl;

//将仿函数的操作结果填写在指定区间
generate(iv.begin(), iv.end(), even_by_two());
for_each(iv.begin(), iv.end(), display<int>());
cout << endl;

generate_n(iv.begin(), 3, even_by_two());
for_each(iv.begin(), iv.end(), display<int>());
cout << endl;

generate_n((iv.begin()+2), 3, fix_val());
for_each(iv.begin(), iv.end(), display<int>());
cout << endl;

//删除指定值的元素，该元素之后的所有元素全部前移，容器结尾会有冗余元素存在，
//需要用户自行处理，函数返回冗余节点的第一个指针
cout << *remove(iv.begin(), iv.end(), 20) << endl;
for_each(iv.begin(), iv.end(), display<int>());
cout << endl;

cout << *remove(iv.begin(), iv.end(), 21) << endl;
for_each(iv.begin(), iv.end(), display<int>());
cout << endl;

//将符合要求的元素全部放置于另一容器，原容器数据不变
//函数返回新容器的最后一个节点
vector<int> iv3(20);        //指定容器初始大小为20个
cout << *remove_copy(iv.begin(), iv.end(), iv3.begin(), 16) << endl;
for_each(iv.begin(), iv.end(), display<int>());
cout << endl;
for_each(iv3.begin(), iv3.end(), display<int>());
cout << endl;

//移除满足条件的元素，容器大小不变，结尾会有冗余元素，函数返回冗余元素的起始位置
cout << *remove_if(iv.begin(), iv.end(), bind2nd(less<int>(), 20)) << endl;
for_each(iv.begin(), iv.end(), display<int>());
cout << endl;
//将满足条件的元素移动到另一个容器中
iv3.clear();
iv3.resize(20);
for_each(iv3.begin(), iv3.end(), display<int>());
cout << endl;
remove_copy_if(iv.begin(), iv.end(), iv3.begin(), bind2nd(less<int>(), 20));
for_each(iv.begin(), iv.end(), display<int>());
cout << endl;
for_each(iv3.begin(), iv3.end(), display<int>());
cout << endl;
//将指定元素值改为另一个值
replace(iv.begin(), iv.end(), 20, 10);
for_each(iv.begin(), iv.end(), display<int>());
cout << endl;

//替换指定元素，替换后，整个序列复制到另一空间
iv3.clear();
iv3.resize(12);
replace_copy(iv.begin(), iv.end(), iv3.begin(), 10, 23);
for_each(iv.begin(), iv.end(), display<int>());
cout << endl;
for_each(iv3.begin(), iv3.end(), display<int>());
cout << endl;

//替换满足某个条件的元素
replace_if(iv.begin(), iv.end(), bind2nd(less<int>(), 20), 20);
for_each(iv.begin(), iv.end(), display<int>());
cout << endl;

//替换满足投个条件的所有元素，将结果放置于另一区间
iv3.clear();
iv3.resize(12);
replace_copy_if(iv.begin(), iv.end(),iv3.begin(), bind2nd(less<int>(), 25), 20);
for_each(iv.begin(), iv.end(), display<int>());
cout << endl;
for_each(iv3.begin(), iv3.end(), display<int>());
cout << endl;

iv.clear();
iv = vector<int>(ia, ia + sizeof(ia) / sizeof(int));
for_each(iv.begin(), iv.end(), display<int>());
cout << endl;

//逆向重排每个元素
reverse(iv.begin(), iv.end());
for_each(iv.begin(), iv.end(), display<int>());
cout << endl;
//逆向重排，结果放置于另一个容器
vector<int> iv4(sizeof(ia) / sizeof(int));
reverse_copy(iv.begin(), iv.end(), iv4.begin());
for_each(iv.begin(), iv.end(), display<int>());
cout << endl;
for_each(iv4.begin(), iv4.end(), display<int>());
cout << endl;

//旋转元素(以指定元素为界限，对调两边的元素）
rotate(iv.begin(), iv.begin() + 4, iv.end());
for_each(iv.begin(), iv.end(), display<int>());
cout << endl;

//对调前后两节元素，但结果存储在指定容器中，原容器不变
iv4.clear();
iv4.resize(sizeof(ia) / sizeof(int));
rotate_copy(iv.begin(), iv.begin() + 4, iv.end(), iv4.begin());
for_each(iv.begin(), iv.end(), display<int>());
cout << endl;
for_each(iv4.begin(), iv4.end(), display<int>());
cout << endl;

//查找某个子序列第一次出现的地址
int ia2[] = { 0,8 };
vector<int> sub(ia2, ia2 + 2);
cout << *search(iv.begin(), iv.end(), sub.begin(), sub.end()) << endl;

//查找连续count个符合条件的元素形成的子序列的开始地址
cout << *search_n(iv.begin(), iv.end(), 2, 8, less<int>()) << endl;
cout << *search_n(iv.begin(), iv.end(), 2, 6) << endl;

//数据交换
cout << "数据交换" << endl;
for_each(iv.begin(), iv.end(), display<int>());
cout << endl;
for_each(sub.begin(), sub.end(), display<int>());
cout << endl;
swap_ranges(sub.begin(), sub.end(), iv.begin());
for_each(iv.begin(), iv.end(), display<int>());
cout << endl;
for_each(sub.begin(), sub.end(), display<int>());
cout << endl;

//改变区间值,全部减2
transform(iv.begin(), iv.end(), iv.begin(), bind2nd(minus<int>(),2));
for_each(iv.begin(), iv.end(), display<int>());
cout << endl;

//将指定区间2的每个元素添加到指定区间1上，结果返回到指定区间3（1,2,3可以相等）
transform(iv.begin(), iv.end(), iv.begin(), iv.begin(), plus<int>());
for_each(iv.begin(), iv.end(), display<int>());
cout << endl;

cout << "******************************" << endl;
vector<int> iv5(ia, ia + sizeof(ia) / sizeof(int));
vector<int> iv6(ia + 4, ia + 8);
vector<int> iv7(15);

cout << "iv5=" << endl;
for_each(iv5.begin(), iv5.end(), display<int>());
cout << endl;
for_each(iv6.begin(), iv6.end(), display<int>());
cout << endl;

cout << binary_search(iv5.begin(), iv5.end(), 2) << endl;

//寻找极值
cout << *max_element(iv5.begin(), iv5.end()) << endl;
cout << *max_element(iv5.begin(), iv5.end()) << endl;

//检查是否是包含关系
cout << includes(iv5.begin(), iv5.end(), iv6.begin(), iv6.end()) << endl;

//将两个可排序序列合并,结果存储到第三个序列
merge(iv5.begin(), iv5.end(), iv6.begin(), iv6.end(),iv7.begin());
for_each(iv7.begin(), iv7.end(), display<int>());
cout << endl;

//将符合条件的元素放在容器前部，不符合的放在后部分
partition(iv7.begin(), iv7.end(), even());
for_each(iv7.begin(), iv7.end(), Display<int>());
cout << endl;

//去除连续而重复的元素，容器尾部会有冗余数据需要手动清理，返回首个冗余数据的地址
unique(iv5.begin(), iv5.end());
for_each(iv5.begin(), iv5.end(), display<int>());
cout << endl;

unique_copy(iv5.begin(), iv5.end(), iv7.begin());

cout << "***********************" << endl;
int i = 5;
//实体对象调用
even ev;
ev(i);

//template
plus<int> pl;
cout << pl(1, 3) << endl;

//无名对象调用
cout << even()(i) << endl;
//template
cout << plus<int>()(1, 3) << endl;
*/
#pragma endregion

#pragma region 模板练习
/*
    double ie = 3.00;
    int iei = 2;
    string ss = "sdfdsf";
    char s[] = { '1','2','3' };
    print_typeof<double>(ie);
    print_typeof<int>(iei);
    print_typeof(ss);
    print_typeof(s);
 */
#pragma endregion

}





// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
